# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
44602 | PowerOfNinjaGo | Worst Reporter 3 (JOI18_worst_reporter3) | C++17 | 1165 ms | 20924 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
int n, q;
const int maxn = 5e5+5;
int arr[maxn];
int mx[maxn];
int team[maxn];
int rng[maxn];
ll intv[maxn];
ll dx[maxn];
vector<int> cap;
ll getPos(int id, int t)
{
int cap = team[id];
int rnd = t/intv[cap];
ll res = -id;
res += rnd*dx[cap];
//printf("getPos(%d, %d) = %lld\n", id, t, res);
return res;
}
int cnt(ll x, int t)
{
int lo = 1, hi = n+1;
while(lo< hi)
{
int mid = (lo+hi)/2;
if(getPos(mid, t)<= x) hi = mid;
else lo = mid+1;
}
//printf("end %d\n", lo);
return n+1-lo;
}
int main()
{
scanf("%d %d", &n, &q);
for(int i = 1; i<= n; i++) scanf("%d", &arr[i]);
for(int i = 1; i<= n; i++)
{
if(arr[i]> mx[i-1])
{
mx[i] = arr[i];
rng[i] = 1;
team[i] = i;
cap.pb(i);
}
else
{
mx[i] = mx[i-1];
rng[i] = rng[i-1]+1;
team[i] = team[i-1];
}
}
for(int i = 0; i< (int) cap.size(); i++)
{
int x = cap[i];
if(i == 0) intv[x] = arr[x], dx[x] = arr[x];
else
{
int w = cap[i-1];
int rnd = (arr[x]+dx[w]-1)/dx[w];
intv[x] = intv[w]*rnd;
dx[x] = dx[w]*rnd;
}
}
while(q--)
{
ll x, y, t; scanf("%lld %lld %lld", &t, &x, &y);
int res = cnt(y, t)-cnt(x-1, t);
if(x<= t && t<= y) res++;
printf("%d\n", res);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |