oj.uz

Submission #994162

# Submission time Handle Problem Language Result Execution time Memory
994162 2024-06-07T08:04:51 Z bachhoangxuan Fish 3 (JOI24_fish3) C++17
100 / 100
 379 ms 58984 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=300005;
const int B=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;

int n,D,c[maxn],p[maxn],cc[maxn],pre[maxn];
int q,ans[maxn];
vector<pii> qq[maxn];

int tree[4*maxn];
int lazy[4*maxn];
void getnew(int l,int r,int id,int val){
    lazy[id]+=val;
    tree[id]+=(r-l+1)*val;
}
void pushdown(int l,int r,int id){
    if(!lazy[id]) return;
    int mid=(l+r)>>1;
    getnew(l,mid,id<<1,lazy[id]);
    getnew(mid+1,r,id<<1|1,lazy[id]);
    lazy[id]=0;
}
void update(int l,int r,int id,int tl,int tr,int val){
    if(tr<l || r<tl) return;
    if(tl<=l && r<=tr){
        getnew(l,r,id,val);
        return;
    }
    pushdown(l,r,id);
    int mid=(l+r)>>1;
    update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
    tree[id]=tree[id<<1]+tree[id<<1|1];
}
int query(int l,int r,int id,int tl,int tr){
    if(tr<l || r<tl) return 0;
    if(tl<=l && r<=tr) return tree[id];
    pushdown(l,r,id);
    int mid=(l+r)>>1;
    return query(l,mid,id<<1,tl,tr)+query(mid+1,r,id<<1|1,tl,tr);
}

void solve(){
    cin >> n >> D;
    for(int i=1;i<=n;i++){
        cin >> c[i];
        if(i>1 && c[i]%D<c[i-1]%D) p[i]++;
        p[i]+=p[i-1];
        cc[i]=c[i]/D-p[i];
        pre[i]=pre[i-1]+cc[i];
        //cout << cc[i] << '\n';
    }
    cin >> q;
    for(int i=1;i<=q;i++){
        int l,r;cin >> l >> r;
        qq[r].push_back({l,i});
    }
    vector<int> v;
    for(int i=1;i<=n;i++){
        while(!v.empty() && cc[v.back()]>=cc[i]){
            int r=v.back();v.pop_back();
            int l=(v.empty()?1:v.back()+1);
            update(1,n,1,l,r,-cc[r]);
        }
        int L=(v.empty()?1:v.back()+1);
        update(1,n,1,L,i,cc[i]);
        v.push_back(i);
        for(auto [l,id]:qq[i]){
            int Min=query(1,n,1,l,l);
            if(Min+p[l]<0) ans[id]=-1;
            else ans[id]=pre[i]-pre[l-1]-query(1,n,1,l,i);
        }
    }
    for(int i=1;i<=q;i++) cout << ans[i] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 5 ms 14940 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 5 ms 15036 KB Output is correct
7 Correct 4 ms 14952 KB Output is correct
8 Correct 4 ms 15084 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 5 ms 14940 KB Output is correct
11 Correct 4 ms 14940 KB Output is correct
12 Correct 4 ms 14936 KB Output is correct
13 Correct 5 ms 14940 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 52048 KB Output is correct
2 Correct 367 ms 51540 KB Output is correct
3 Correct 84 ms 27476 KB Output is correct
4 Correct 267 ms 51188 KB Output is correct
5 Correct 281 ms 51028 KB Output is correct
6 Correct 315 ms 50900 KB Output is correct
7 Correct 301 ms 51028 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 31312 KB Output is correct
2 Correct 371 ms 58704 KB Output is correct
3 Correct 370 ms 58704 KB Output is correct
4 Correct 379 ms 58904 KB Output is correct
5 Correct 360 ms 58704 KB Output is correct
6 Correct 351 ms 52304 KB Output is correct
7 Correct 374 ms 52232 KB Output is correct
8 Correct 364 ms 55632 KB Output is correct
9 Correct 376 ms 55668 KB Output is correct
10 Correct 306 ms 57540 KB Output is correct
11 Correct 307 ms 56160 KB Output is correct
12 Correct 326 ms 57288 KB Output is correct
13 Correct 339 ms 57176 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 42552 KB Output is correct
2 Correct 327 ms 52048 KB Output is correct
3 Correct 210 ms 34820 KB Output is correct
4 Correct 351 ms 55360 KB Output is correct
5 Correct 334 ms 57408 KB Output is correct
6 Correct 351 ms 58704 KB Output is correct
7 Correct 320 ms 48436 KB Output is correct
8 Correct 348 ms 58704 KB Output is correct
9 Correct 289 ms 51404 KB Output is correct
10 Correct 254 ms 51212 KB Output is correct
11 Correct 364 ms 55208 KB Output is correct
12 Correct 295 ms 54608 KB Output is correct
13 Correct 359 ms 58432 KB Output is correct
14 Correct 260 ms 54356 KB Output is correct
15 Correct 364 ms 58440 KB Output is correct
16 Correct 264 ms 54352 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 5 ms 14940 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 5 ms 15036 KB Output is correct
7 Correct 4 ms 14952 KB Output is correct
8 Correct 4 ms 15084 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 5 ms 14940 KB Output is correct
11 Correct 4 ms 14940 KB Output is correct
12 Correct 4 ms 14936 KB Output is correct
13 Correct 5 ms 14940 KB Output is correct
14 Correct 370 ms 52048 KB Output is correct
15 Correct 367 ms 51540 KB Output is correct
16 Correct 84 ms 27476 KB Output is correct
17 Correct 267 ms 51188 KB Output is correct
18 Correct 281 ms 51028 KB Output is correct
19 Correct 315 ms 50900 KB Output is correct
20 Correct 301 ms 51028 KB Output is correct
21 Correct 129 ms 31312 KB Output is correct
22 Correct 371 ms 58704 KB Output is correct
23 Correct 370 ms 58704 KB Output is correct
24 Correct 379 ms 58904 KB Output is correct
25 Correct 360 ms 58704 KB Output is correct
26 Correct 351 ms 52304 KB Output is correct
27 Correct 374 ms 52232 KB Output is correct
28 Correct 364 ms 55632 KB Output is correct
29 Correct 376 ms 55668 KB Output is correct
30 Correct 306 ms 57540 KB Output is correct
31 Correct 307 ms 56160 KB Output is correct
32 Correct 326 ms 57288 KB Output is correct
33 Correct 339 ms 57176 KB Output is correct
34 Correct 301 ms 42552 KB Output is correct
35 Correct 327 ms 52048 KB Output is correct
36 Correct 210 ms 34820 KB Output is correct
37 Correct 351 ms 55360 KB Output is correct
38 Correct 334 ms 57408 KB Output is correct
39 Correct 351 ms 58704 KB Output is correct
40 Correct 320 ms 48436 KB Output is correct
41 Correct 348 ms 58704 KB Output is correct
42 Correct 289 ms 51404 KB Output is correct
43 Correct 254 ms 51212 KB Output is correct
44 Correct 364 ms 55208 KB Output is correct
45 Correct 295 ms 54608 KB Output is correct
46 Correct 359 ms 58432 KB Output is correct
47 Correct 260 ms 54356 KB Output is correct
48 Correct 364 ms 58440 KB Output is correct
49 Correct 264 ms 54352 KB Output is correct
50 Correct 373 ms 58740 KB Output is correct
51 Correct 342 ms 52560 KB Output is correct
52 Correct 348 ms 55636 KB Output is correct
53 Correct 300 ms 56308 KB Output is correct
54 Correct 328 ms 57280 KB Output is correct
55 Correct 368 ms 58984 KB Output is correct
56 Correct 257 ms 54356 KB Output is correct
57 Correct 262 ms 51024 KB Output is correct
58 Correct 247 ms 51284 KB Output is correct
59 Correct 352 ms 56504 KB Output is correct
60 Correct 260 ms 54356 KB Output is correct
61 Correct 297 ms 57020 KB Output is correct
62 Correct 342 ms 53936 KB Output is correct
63 Correct 327 ms 57168 KB Output is correct
64 Correct 263 ms 54444 KB Output is correct