Header Ad

HackerEarth Xenny and Formula 0 problem solution

In this HackerEarth Xenny and Formula 0 problem-solution, Xenny drove in a popular racing championship called Formula 0. His long-distant friend Mr. Kmcode had made a racing track for him in RSQLand. To entertain the public, he used to keep a drag racing event at the Kmcode Track before every race. The Kmcode Track was circular and there were N grandstands along the track, numbered from 1 to N, separated by 1 angular unit each.
Initially, stand i contained Ai people.
In each drag race, he started from stand number X with an initial angular velocity of magnitude w angular units per second. At the end of each second, his car's angular velocity decreased by a magnitude of d angular units per second. His car always came to a halt when its angular velocity reached equal to or below zero.
In each race, Xenny counted the total number of people in stands that he crossed in that race and reported its value modulo 109 + 7, to his team.
Whenever Xenny started his race from a particular stand X, at the end of the race, his team increased the number of passes for his races and hence, Y people were added to stand number X after the race.
Given the data for R races, print the number that Xenny reported to his team in each race.



HackerEarth Xenny and Formula 0 problem solution


HackerEarth Xenny and Formula 0 problem solution.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <stdio.h>
#define MOD 1000000007
using namespace std;

typedef long long ll;

const ll N = 1e5 + 10; // limit for array size
ll n; // array size
ll t[4 * N];

void build() { // build the tree
for (ll i = n - 1; i > 0; --i) t[i] = (t[i<<1] + t[i<<1|1]) % MOD;;
}

void modify(ll p, ll value) { // set value at position p
for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = (t[p] + t[p^1]) % MOD;
}

ll query(ll l, ll r) { // sum on llerval [l, r)
ll res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) res = (res + t[l++]) % MOD;
if (r&1) res = (res + t[--r]) % MOD;
}
return res;
}

int main()
{
ll r; cin >> r >> n;
for(ll i=0;i<n;i++) scanf("%lld", t + n + i);
build();
ll x, w, d, y;
ll L, dist;
ll ret;
while(r--) {
cin >> x >> w >> d >> y;
L = x;
dist = (w * w) / (2 * d);
ll complete_circles = dist / n;
ll extra = dist % n;
ret = ((complete_circles % MOD) * (query(0, n) % MOD)) % MOD;
// X to N
ret = (ret + (query(L - 1, min(n, L + extra)) % MOD)) % MOD;
// 1 to (dist - (N - X))
if(L + extra > n) {
ret = (ret + (query(0, extra - (n - L)) % MOD)) % MOD;
}
cout << ret % MOD<< "\n";
modify(x - 1, t[n + x - 1] + y);
}
}

Second solution

#includeiostream
#includecstdio
#includecstring
#includestring
#includecctype
#includecstdlib
#includealgorithm
#includebitset
#includevector
#includelist
#includedeque
#includequeue
#includemap
#includeset
#includestack
#includecmath
#includesstream
#includefstream
#includeiomanip
#includectime
#includecomplex
#includefunctional
#includeclimits
#includecassert
#includeiterator
#includeunordered_map
#includeunordered_set
#includequadmath.h
using namespace std;

namespace test{
void end_test(){
int val;
if (cin val){
exit(1);
}
}
void range_test(int t, int l, int r){
if (t l r t){
exit(1);
}
}
}
#define MAX 100002
const __int128 MOD = 1000000007LL;
__int128 seg[MAX 4];
__int128 a[MAX];
inline void init(int b, int l, int r){
if (l + 1 == r){
seg[b] = a[l];
return;
}
init(b 2 + 1, l, (l + r) 1);
init(b 2 + 2, (l + r) 1, r);
seg[b] = seg[b 2 + 1] + seg[b 2 + 2];
seg[b] %= MOD;
}
inline void add(int b, int l, int r, int ll, __int128 x){
if (l = ll&&ll r&&l + 1 == r){
seg[b] += x;
seg[b] %= MOD;
return;
}
if (l = ll&&ll r){
add(b 2 + 1, l, (l + r) 1, ll, x);
add(b 2 + 2, (l + r) 1, r, ll, x);
seg[b] = seg[b 2 + 1] + seg[b 2 + 2];
seg[b] %= MOD;
}
}

inline __int128 qq(int b, int l, int r, int ll, int rr){
if (ll = l&&r = rr){
return seg[b];
}
if (r = ll rr = l){
return 0;
}
return (qq(b 2 + 1, l, (l + r) 1, ll, rr) + qq(b 2 + 2, (l + r) 1, r, ll, rr)) % MOD;
}
__int128 r;
__int128 n;
__int128 range_sum(int l, int r){

if (l = r){
return qq(0, 0, n, l, r + 1);
}
else{
return (qq(0, 0, n, l, n) + qq(0, 0, n, 0, r + 1)) % MOD;
}
}


int main(){
int buf;
scanf(%d, &buf);
r = buf;
scanf(%d, &buf);
n = buf;
testrange_test(r, 1, 100000);
testrange_test(n, 1, 100000);
for (int i = 0; i n; i++){
long long int k;
scanf(%lld, &k);
a[i] = k;
}
init(0, 0, n);
while (r--){
__int128 x, w, d, y;
long long int xx, ww, dd, yy;
scanf(%lld%lld%lld%lld, &xx, &ww, &dd, &yy);
x = xx;
w = ww;
d = dd;
y = yy;
testrange_test(x, 1, n);
testrange_test(w, 2, 1000000000);
testrange_test(d, 1, 1000000000);
testrange_test(y, 1, 100);
x--;
__int128 index = x;
__int128 ans = 0;
__int128 D = d;
__int128 sum = w + w - (wd)d;
__int128 ad1 = 1;
sum = (wd)+ad1;
__int128 ad2 = 2;
sum = ad2;
w = sum;
__int128 v = w(__int128)(n);
v %= MOD;
ans += range_sum(0, n - 1)v;
ans %= MOD;
v = w % (__int128)(n);
__int128 star = index;
__int128 en = ((__int128)(v)+(long long int)(index)) % (__int128)(n);
ans += range_sum(star, en);
ans %= MOD;
if (ans0LL){
return 1;
}
add(0, 0, n, x, y);
long long int outt = ans;
printf(%lldn, outt);
}
testend_test();
return 0;
}


Post a Comment

0 Comments