oj.uz

Submission #992278

# Submission time Handle Problem Language Result Execution time Memory
992278 2024-06-04T08:14:39 Z imarn Fish 3 (JOI24_fish3) C++14
100 / 100
 1232 ms 61580 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int mxn=3e5+5;
ll t[4*mxn]{0},lz[4*mxn]{0};
void push(int i,int l,int r){
    if(lz[i]==1e16)return;
    t[i]=lz[i]*(r-l+1);
    if(l<r)lz[2*i]=lz[i],lz[2*i+1]=lz[i];
    lz[i]=1e16;
}
void update(int i,int l,int r,int tl,int tr,ll v){
    push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lz[i]=v;push(i,l,r);return;
    }int m=(l+r)>>1;
    update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v);
    t[i]=t[2*i]+t[2*i+1];
}
ll query(int i,int l,int r,int tl,int tr){
    push(i,l,r);
    if(r<tl||l>tr)return 0;
    if(r<=tr&&l>=tl)return t[i];
    int m=(l+r)>>1;
    return query(2*i,l,m,tl,tr)+query(2*i+1,m+1,r,tl,tr);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;ll d;cin>>n>>d;ll c[n+1],a[n+1],b[n+1],qa[n+1];
    for(int i=1;i<=4*n;i++)lz[i]=1e16;
    for(int i=1;i<=n;i++){
        cin>>c[i];b[i]=c[i]%d,a[i]=c[i]/d;
    }ll pf[n+1]={0},spf[n+1]={0};
    for(int i=2;i<=n;i++)pf[i]=pf[i-1]+(b[i]<b[i-1]);
    for(int i=1;i<=n;i++)spf[i]=spf[i-1]+pf[i],qa[i]=qa[i-1]+a[i];
    vector<pii>qr[n+1];int q;cin>>q;ll ans[q+1]={0};
    for(int i=1;i<=q;i++){
        int l,r;cin>>l>>r;qr[r].pb({l,i});
    }vector<pii>g;
    for(int i=1;i<=n;i++){
        int l=1,r=i;
        while(l<r){
            int m=(l+r)>>1;
            if(query(1,1,n,m,m)>a[i]-pf[i])r=m;
            else l=m+1;
        }update(1,1,n,l,i,a[i]-pf[i]);
        for(auto it : qr[i]){
            ans[it.s]=qa[i]-qa[it.f-1];
            ans[it.s]-=query(1,1,n,it.f,i);
            ans[it.s]-=spf[i]-spf[it.f-1];
            if(query(1,1,n,it.f,it.f)+pf[it.f]<0)ans[it.s]=-1;
        }
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 7 ms 2972 KB Output is correct
5 Correct 6 ms 2792 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 5 ms 2800 KB Output is correct
8 Correct 6 ms 2908 KB Output is correct
9 Correct 7 ms 2908 KB Output is correct
10 Correct 7 ms 2908 KB Output is correct
11 Correct 6 ms 2908 KB Output is correct
12 Correct 5 ms 2908 KB Output is correct
13 Correct 6 ms 2976 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1075 ms 50308 KB Output is correct
2 Correct 1093 ms 49748 KB Output is correct
3 Correct 140 ms 9932 KB Output is correct
4 Correct 1177 ms 49348 KB Output is correct
5 Correct 1198 ms 49236 KB Output is correct
6 Correct 1094 ms 49232 KB Output is correct
7 Correct 1091 ms 49232 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 13756 KB Output is correct
2 Correct 1171 ms 61524 KB Output is correct
3 Correct 1232 ms 61524 KB Output is correct
4 Correct 1137 ms 61540 KB Output is correct
5 Correct 1191 ms 61332 KB Output is correct
6 Correct 1112 ms 55088 KB Output is correct
7 Correct 1106 ms 54872 KB Output is correct
8 Correct 1112 ms 58284 KB Output is correct
9 Correct 1170 ms 58284 KB Output is correct
10 Correct 1117 ms 56716 KB Output is correct
11 Correct 1137 ms 56728 KB Output is correct
12 Correct 1107 ms 59808 KB Output is correct
13 Correct 1079 ms 59792 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 42064 KB Output is correct
2 Correct 1208 ms 50316 KB Output is correct
3 Correct 385 ms 19784 KB Output is correct
4 Correct 1219 ms 58028 KB Output is correct
5 Correct 1089 ms 58304 KB Output is correct
6 Correct 1200 ms 61528 KB Output is correct
7 Correct 909 ms 51272 KB Output is correct
8 Correct 1136 ms 61264 KB Output is correct
9 Correct 1108 ms 54100 KB Output is correct
10 Correct 1092 ms 53780 KB Output is correct
11 Correct 1115 ms 57900 KB Output is correct
12 Correct 1153 ms 57372 KB Output is correct
13 Correct 1126 ms 61084 KB Output is correct
14 Correct 1084 ms 56916 KB Output is correct
15 Correct 1131 ms 61092 KB Output is correct
16 Correct 1128 ms 56916 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 7 ms 2972 KB Output is correct
5 Correct 6 ms 2792 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 5 ms 2800 KB Output is correct
8 Correct 6 ms 2908 KB Output is correct
9 Correct 7 ms 2908 KB Output is correct
10 Correct 7 ms 2908 KB Output is correct
11 Correct 6 ms 2908 KB Output is correct
12 Correct 5 ms 2908 KB Output is correct
13 Correct 6 ms 2976 KB Output is correct
14 Correct 1075 ms 50308 KB Output is correct
15 Correct 1093 ms 49748 KB Output is correct
16 Correct 140 ms 9932 KB Output is correct
17 Correct 1177 ms 49348 KB Output is correct
18 Correct 1198 ms 49236 KB Output is correct
19 Correct 1094 ms 49232 KB Output is correct
20 Correct 1091 ms 49232 KB Output is correct
21 Correct 164 ms 13756 KB Output is correct
22 Correct 1171 ms 61524 KB Output is correct
23 Correct 1232 ms 61524 KB Output is correct
24 Correct 1137 ms 61540 KB Output is correct
25 Correct 1191 ms 61332 KB Output is correct
26 Correct 1112 ms 55088 KB Output is correct
27 Correct 1106 ms 54872 KB Output is correct
28 Correct 1112 ms 58284 KB Output is correct
29 Correct 1170 ms 58284 KB Output is correct
30 Correct 1117 ms 56716 KB Output is correct
31 Correct 1137 ms 56728 KB Output is correct
32 Correct 1107 ms 59808 KB Output is correct
33 Correct 1079 ms 59792 KB Output is correct
34 Correct 969 ms 42064 KB Output is correct
35 Correct 1208 ms 50316 KB Output is correct
36 Correct 385 ms 19784 KB Output is correct
37 Correct 1219 ms 58028 KB Output is correct
38 Correct 1089 ms 58304 KB Output is correct
39 Correct 1200 ms 61528 KB Output is correct
40 Correct 909 ms 51272 KB Output is correct
41 Correct 1136 ms 61264 KB Output is correct
42 Correct 1108 ms 54100 KB Output is correct
43 Correct 1092 ms 53780 KB Output is correct
44 Correct 1115 ms 57900 KB Output is correct
45 Correct 1153 ms 57372 KB Output is correct
46 Correct 1126 ms 61084 KB Output is correct
47 Correct 1084 ms 56916 KB Output is correct
48 Correct 1131 ms 61092 KB Output is correct
49 Correct 1128 ms 56916 KB Output is correct
50 Correct 1160 ms 61480 KB Output is correct
51 Correct 1139 ms 55120 KB Output is correct
52 Correct 1129 ms 58152 KB Output is correct
53 Correct 1081 ms 56660 KB Output is correct
54 Correct 1197 ms 59988 KB Output is correct
55 Correct 1136 ms 61580 KB Output is correct
56 Correct 1174 ms 56916 KB Output is correct
57 Correct 1214 ms 53844 KB Output is correct
58 Correct 1199 ms 53844 KB Output is correct
59 Correct 1208 ms 59312 KB Output is correct
60 Correct 1212 ms 56916 KB Output is correct
61 Correct 1093 ms 56660 KB Output is correct
62 Correct 1108 ms 56724 KB Output is correct
63 Correct 1117 ms 59676 KB Output is correct
64 Correct 1132 ms 56968 KB Output is correct