oj.uz

Submission #835534

# Submission time Handle Problem Language Result Execution time Memory
835534 2023-08-23T15:32:45 Z fdnfksd Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 313 ms 37060 KB 
#include<bits/stdc++.h>
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll get(ll i,ll j,ll l,ll r)
{
    return max(min(j,r)-max(i,l)+1,0ll);
}
ll n,q,jump[maxN],d[maxN],nxt[maxN],m[maxN];
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> d[i],jump[i]=d[i];
    for(int i=2;i<=n;i++)
    {
        ll x=jump[i-1];
        ll y=(d[i]+x-1)/x*x;
        jump[i]=y;
        m[i]=jump[i]/jump[i-1];
    }
    nxt[n]=n;
    for(int i=n-1;i>=1;i--)
    {
        nxt[i]=nxt[i+1];
        if(jump[i]!=jump[i+1]) nxt[i]=i;
    }
    for(int i=1;i<=q;i++)
    {
        ll l,r,t;
        cin >> t >> l >> r;
        ll luot=t/d[1];
        ll vd=luot*d[1]-1;
        ll ans=0;
        if(vd>=l&&vd<=r) ans=1;
        ll cur=2;
        while(cur<=n)
        {
            ll x=jump[cur];
            luot/=m[cur];
            ll cc=luot*jump[cur];
            ans+=get(l,r,cc-nxt[cur],cc-cur);
            cur=nxt[cur]+1;
        }
        ans+=((t>=l)&&(t<=r));
        cout << ans << '\n';
    }

}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

worst_reporter3.cpp: In function 'void solve()':
worst_reporter3.cpp:45:16: warning: unused variable 'x' [-Wunused-variable]
   45 |             ll x=jump[cur];
      |                ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 33708 KB Output is correct
2 Correct 203 ms 34392 KB Output is correct
3 Correct 201 ms 34452 KB Output is correct
4 Correct 189 ms 34400 KB Output is correct
5 Correct 203 ms 34364 KB Output is correct
6 Correct 271 ms 34420 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 33708 KB Output is correct
2 Correct 203 ms 34392 KB Output is correct
3 Correct 201 ms 34452 KB Output is correct
4 Correct 189 ms 34400 KB Output is correct
5 Correct 203 ms 34364 KB Output is correct
6 Correct 271 ms 34420 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 195 ms 32844 KB Output is correct
14 Correct 196 ms 33424 KB Output is correct
15 Correct 179 ms 32160 KB Output is correct
16 Correct 214 ms 32736 KB Output is correct
17 Correct 248 ms 36984 KB Output is correct
18 Correct 255 ms 36888 KB Output is correct
19 Correct 273 ms 37000 KB Output is correct
20 Correct 258 ms 36900 KB Output is correct
21 Correct 313 ms 37004 KB Output is correct
22 Correct 259 ms 37060 KB Output is correct
23 Correct 247 ms 36852 KB Output is correct
24 Correct 265 ms 36992 KB Output is correct
25 Correct 241 ms 34392 KB Output is correct
26 Correct 219 ms 34332 KB Output is correct
27 Correct 261 ms 36552 KB Output is correct
28 Correct 290 ms 36780 KB Output is correct
29 Correct 273 ms 36312 KB Output is correct
30 Correct 267 ms 36552 KB Output is correct
31 Correct 273 ms 36784 KB Output is correct
32 Correct 182 ms 33008 KB Output is correct
33 Correct 1 ms 340 KB Output is correct