oj.uz

Submission #843541

# Submission time Handle Problem Language Result Execution time Memory
843541 2023-09-04T04:32:52 Z pdm Fish 2 (JOI22_fish2) C++14
100 / 100
 580 ms 441424 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),
- 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<pii,int>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e9;
const int mod=1e9+7;
const int maxn=100005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=500005;
const int maxl=35;
const int maxa=250000;
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,f[maxn];
struct node{
    int pl[maxl],pr[maxl],cl[maxl],cr[maxl],sl[maxl],sr[maxl];
    int szl,szr,sum,cnt;
    node(){}
    void reset(int x){
        szl=szr=1;
        pl[0]=pr[0]=x;
        sl[0]=sr[0]=cl[0]=cr[0]=0;
        sum=f[x];cnt=1;
    }
    void print(int l,int r){
        cout << '*' << l << ' ' << r << '\n';
        cout << sum << ' ' << cnt << '\n';
        cout << "#rr\n";
        for(int i=0;i<szr;i++) cout << pr[i] << ' ' << cr[i] << ' ' << sr[i] << '\n';
        cout << "#ll\n";
        for(int i=0;i<szl;i++) cout << pl[i] << ' ' << cl[i] << ' ' << sl[i] << '\n';
    }
};

namespace Segtree{
    node tree[4*maxn];
    node s[2];
    int st=-1;
    int add(int a,int b){
        return min(a+b,inf);
    }
    void merge(node &res,node &a,node &b){
        res.szl=a.szl;res.szr=b.szr;
        res.sum=a.sum+b.sum;
        res.cnt=0;
        for(int i=0;i<res.szl;i++) res.pl[i]=a.pl[i],res.cl[i]=a.cl[i],res.sl[i]=a.sl[i];
        for(int i=0;i<res.szr;i++) res.pr[i]=b.pr[i],res.cr[i]=b.cr[i],res.sr[i]=b.sr[i];
        int len=0,ok=0;
        if(a.sum>b.sum){
            int cur=b.sum;len=res.szr;ok=0;
            for(int i=0;i<a.szr;i++){
                if(cur+a.sr[i]<f[a.pr[i]]){
                    res.pr[res.szr]=a.pr[i];
                    res.sr[res.szr]=add(cur,a.sr[i]);
                    res.cr[res.szr++]=0;
                }
            }
        }
        else{
            int cur=a.sum;len=res.szl;ok=1;
            for(int i=0;i<b.szl;i++){
                if(cur+b.sl[i]<f[b.pl[i]]){
                    res.pl[res.szl]=b.pl[i];
                    res.sl[res.szl]=add(cur,b.sl[i]);
                    res.cl[res.szl++]=0;
                }
            }
        }
        b.sl[b.szl]=b.sum;b.cl[b.szl]=b.cnt;
        a.sr[a.szr]=a.sum;a.cr[a.szr]=a.cnt;
        int ca=0,cb=0,cc=len;
        auto fix = [&](int val){
            while(true){
                if(ca<a.szr && a.sr[ca]+b.sl[cb]>=f[a.pr[ca]]) ca++;
                else if(cb<b.szl && a.sr[ca]+b.sl[cb]>=f[b.pl[cb]]) cb++;
                else break;
            }
            if(ok && ca==a.szr){
                while(cc<res.szl && (cb==b.szl || res.pl[cc]<b.pl[cb])) cc++;
                if(cc<res.szl) res.cl[cc]+=val;
                else res.cnt+=val;
            }
            if(!ok && cb==b.szl){
                while(cc<res.szr && (ca==a.szr || res.pr[cc]>a.pr[ca])) cc++;
                if(cc<res.szr) res.cr[cc]+=val;
                else res.cnt+=val;
            }
        };
        for(int i=1;i<=a.szr;i++){
            ca=max(ca,i);
            fix(a.cr[i]);
        }
        ca=cb=0;cc=len;
        for(int i=1;i<=b.szl;i++){
            cb=max(cb,i);
            fix(b.cl[i]);
        }
    }
    void query(int l,int r,int id,int tl,int tr){
        if(r<tl || tr<l) return;
        if(tl<=l && r<=tr){
            if(st==-1) s[0]=tree[id],st=0;
            else st^=1,merge(s[st],s[st^1],tree[id]);
            return;
        }
        int mid=(l+r)>>1;
        query(l,mid,id<<1,tl,tr);query(mid+1,r,id<<1|1,tl,tr);
    }
    int query(int l,int r){
        st=-1;query(1,n,1,l,r);
        return s[st].cnt;
    }
    void update(int l,int r,int id,int pos){
        if(l==r){
            tree[id].reset(l);
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) update(l,mid,id<<1,pos);
        else update(mid+1,r,id<<1|1,pos);
        merge(tree[id],tree[id<<1],tree[id<<1|1]);
    }
    void build(int l,int r,int id){
        if(l==r){
            tree[id].reset(l);
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,id<<1);build(mid+1,r,id<<1|1);
        merge(tree[id],tree[id<<1],tree[id<<1|1]);
        //tree[id].print(l,r);
    }
}
void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> f[i];
    Segtree::build(1,n,1);
    int q;cin >> q;
    for(int i=1;i<=q;i++){
        int t,x,y;cin >> t >> x >> y;
        if(t==1) f[x]=y,Segtree::update(1,n,1,x);
        else cout << Segtree::query(x,y) << '\n';
    }
}
signed main(){
    //freopen("input.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 2 ms 2648 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2652 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 72 ms 440308 KB Output is correct
3 Correct 61 ms 440400 KB Output is correct
4 Correct 62 ms 440400 KB Output is correct
5 Correct 68 ms 440288 KB Output is correct
6 Correct 57 ms 440400 KB Output is correct
7 Correct 68 ms 440400 KB Output is correct
8 Correct 69 ms 440528 KB Output is correct
9 Correct 64 ms 440400 KB Output is correct
10 Correct 71 ms 440392 KB Output is correct
11 Correct 59 ms 440400 KB Output is correct
12 Correct 61 ms 440320 KB Output is correct
13 Correct 63 ms 440416 KB Output is correct
14 Correct 60 ms 440532 KB Output is correct
15 Correct 60 ms 440404 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 2 ms 2648 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2652 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 72 ms 440308 KB Output is correct
23 Correct 61 ms 440400 KB Output is correct
24 Correct 62 ms 440400 KB Output is correct
25 Correct 68 ms 440288 KB Output is correct
26 Correct 57 ms 440400 KB Output is correct
27 Correct 68 ms 440400 KB Output is correct
28 Correct 69 ms 440528 KB Output is correct
29 Correct 64 ms 440400 KB Output is correct
30 Correct 71 ms 440392 KB Output is correct
31 Correct 59 ms 440400 KB Output is correct
32 Correct 61 ms 440320 KB Output is correct
33 Correct 63 ms 440416 KB Output is correct
34 Correct 60 ms 440532 KB Output is correct
35 Correct 60 ms 440404 KB Output is correct
36 Correct 65 ms 440424 KB Output is correct
37 Correct 65 ms 440368 KB Output is correct
38 Correct 63 ms 440400 KB Output is correct
39 Correct 71 ms 440524 KB Output is correct
40 Correct 62 ms 440400 KB Output is correct
41 Correct 60 ms 440532 KB Output is correct
42 Correct 63 ms 440316 KB Output is correct
43 Correct 71 ms 440404 KB Output is correct
44 Correct 60 ms 440288 KB Output is correct
45 Correct 78 ms 440492 KB Output is correct
46 Correct 79 ms 440356 KB Output is correct
47 Correct 65 ms 440528 KB Output is correct
48 Correct 60 ms 440380 KB Output is correct
49 Correct 59 ms 440368 KB Output is correct
50 Correct 71 ms 440404 KB Output is correct
51 Correct 69 ms 440400 KB Output is correct
52 Correct 75 ms 440404 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 72 ms 440308 KB Output is correct
3 Correct 61 ms 440400 KB Output is correct
4 Correct 62 ms 440400 KB Output is correct
5 Correct 68 ms 440288 KB Output is correct
6 Correct 57 ms 440400 KB Output is correct
7 Correct 68 ms 440400 KB Output is correct
8 Correct 69 ms 440528 KB Output is correct
9 Correct 64 ms 440400 KB Output is correct
10 Correct 71 ms 440392 KB Output is correct
11 Correct 59 ms 440400 KB Output is correct
12 Correct 61 ms 440320 KB Output is correct
13 Correct 63 ms 440416 KB Output is correct
14 Correct 60 ms 440532 KB Output is correct
15 Correct 60 ms 440404 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 561 ms 440900 KB Output is correct
18 Correct 456 ms 440828 KB Output is correct
19 Correct 533 ms 440824 KB Output is correct
20 Correct 580 ms 440812 KB Output is correct
21 Correct 557 ms 440852 KB Output is correct
22 Correct 428 ms 440912 KB Output is correct
23 Correct 543 ms 441244 KB Output is correct
24 Correct 551 ms 441048 KB Output is correct
25 Correct 575 ms 441172 KB Output is correct
26 Correct 536 ms 440720 KB Output is correct
27 Correct 330 ms 440912 KB Output is correct
28 Correct 283 ms 440912 KB Output is correct
29 Correct 279 ms 440912 KB Output is correct
30 Correct 380 ms 440712 KB Output is correct
31 Correct 380 ms 440656 KB Output is correct
32 Correct 519 ms 440920 KB Output is correct
33 Correct 555 ms 440912 KB Output is correct
34 Correct 507 ms 440776 KB Output is correct
35 Correct 488 ms 440832 KB Output is correct
36 Correct 532 ms 440912 KB Output is correct
37 Correct 257 ms 440916 KB Output is correct
38 Correct 235 ms 440656 KB Output is correct
39 Correct 312 ms 441424 KB Output is correct
40 Correct 272 ms 441012 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 72 ms 440308 KB Output is correct
3 Correct 61 ms 440400 KB Output is correct
4 Correct 62 ms 440400 KB Output is correct
5 Correct 68 ms 440288 KB Output is correct
6 Correct 57 ms 440400 KB Output is correct
7 Correct 68 ms 440400 KB Output is correct
8 Correct 69 ms 440528 KB Output is correct
9 Correct 64 ms 440400 KB Output is correct
10 Correct 71 ms 440392 KB Output is correct
11 Correct 59 ms 440400 KB Output is correct
12 Correct 61 ms 440320 KB Output is correct
13 Correct 63 ms 440416 KB Output is correct
14 Correct 60 ms 440532 KB Output is correct
15 Correct 60 ms 440404 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 361 ms 440404 KB Output is correct
18 Correct 320 ms 440404 KB Output is correct
19 Correct 275 ms 440656 KB Output is correct
20 Correct 255 ms 440660 KB Output is correct
21 Correct 362 ms 440400 KB Output is correct
22 Correct 326 ms 440400 KB Output is correct
23 Correct 362 ms 440676 KB Output is correct
24 Correct 312 ms 440472 KB Output is correct
25 Correct 333 ms 440780 KB Output is correct
26 Correct 203 ms 440660 KB Output is correct
27 Correct 257 ms 440656 KB Output is correct
28 Correct 236 ms 440656 KB Output is correct
29 Correct 225 ms 440656 KB Output is correct
30 Correct 262 ms 440400 KB Output is correct
31 Correct 285 ms 440912 KB Output is correct
32 Correct 315 ms 440400 KB Output is correct
33 Correct 319 ms 440596 KB Output is correct
34 Correct 310 ms 440524 KB Output is correct
35 Correct 292 ms 440656 KB Output is correct
36 Correct 288 ms 441180 KB Output is correct
37 Correct 259 ms 440572 KB Output is correct
38 Correct 195 ms 440748 KB Output is correct
39 Correct 213 ms 440692 KB Output is correct
40 Correct 130 ms 440912 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 2 ms 2648 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2652 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 72 ms 440308 KB Output is correct
23 Correct 61 ms 440400 KB Output is correct
24 Correct 62 ms 440400 KB Output is correct
25 Correct 68 ms 440288 KB Output is correct
26 Correct 57 ms 440400 KB Output is correct
27 Correct 68 ms 440400 KB Output is correct
28 Correct 69 ms 440528 KB Output is correct
29 Correct 64 ms 440400 KB Output is correct
30 Correct 71 ms 440392 KB Output is correct
31 Correct 59 ms 440400 KB Output is correct
32 Correct 61 ms 440320 KB Output is correct
33 Correct 63 ms 440416 KB Output is correct
34 Correct 60 ms 440532 KB Output is correct
35 Correct 60 ms 440404 KB Output is correct
36 Correct 65 ms 440424 KB Output is correct
37 Correct 65 ms 440368 KB Output is correct
38 Correct 63 ms 440400 KB Output is correct
39 Correct 71 ms 440524 KB Output is correct
40 Correct 62 ms 440400 KB Output is correct
41 Correct 60 ms 440532 KB Output is correct
42 Correct 63 ms 440316 KB Output is correct
43 Correct 71 ms 440404 KB Output is correct
44 Correct 60 ms 440288 KB Output is correct
45 Correct 78 ms 440492 KB Output is correct
46 Correct 79 ms 440356 KB Output is correct
47 Correct 65 ms 440528 KB Output is correct
48 Correct 60 ms 440380 KB Output is correct
49 Correct 59 ms 440368 KB Output is correct
50 Correct 71 ms 440404 KB Output is correct
51 Correct 69 ms 440400 KB Output is correct
52 Correct 75 ms 440404 KB Output is correct
53 Correct 1 ms 344 KB Output is correct
54 Correct 561 ms 440900 KB Output is correct
55 Correct 456 ms 440828 KB Output is correct
56 Correct 533 ms 440824 KB Output is correct
57 Correct 580 ms 440812 KB Output is correct
58 Correct 557 ms 440852 KB Output is correct
59 Correct 428 ms 440912 KB Output is correct
60 Correct 543 ms 441244 KB Output is correct
61 Correct 551 ms 441048 KB Output is correct
62 Correct 575 ms 441172 KB Output is correct
63 Correct 536 ms 440720 KB Output is correct
64 Correct 330 ms 440912 KB Output is correct
65 Correct 283 ms 440912 KB Output is correct
66 Correct 279 ms 440912 KB Output is correct
67 Correct 380 ms 440712 KB Output is correct
68 Correct 380 ms 440656 KB Output is correct
69 Correct 519 ms 440920 KB Output is correct
70 Correct 555 ms 440912 KB Output is correct
71 Correct 507 ms 440776 KB Output is correct
72 Correct 488 ms 440832 KB Output is correct
73 Correct 532 ms 440912 KB Output is correct
74 Correct 257 ms 440916 KB Output is correct
75 Correct 235 ms 440656 KB Output is correct
76 Correct 312 ms 441424 KB Output is correct
77 Correct 272 ms 441012 KB Output is correct
78 Correct 0 ms 344 KB Output is correct
79 Correct 361 ms 440404 KB Output is correct
80 Correct 320 ms 440404 KB Output is correct
81 Correct 275 ms 440656 KB Output is correct
82 Correct 255 ms 440660 KB Output is correct
83 Correct 362 ms 440400 KB Output is correct
84 Correct 326 ms 440400 KB Output is correct
85 Correct 362 ms 440676 KB Output is correct
86 Correct 312 ms 440472 KB Output is correct
87 Correct 333 ms 440780 KB Output is correct
88 Correct 203 ms 440660 KB Output is correct
89 Correct 257 ms 440656 KB Output is correct
90 Correct 236 ms 440656 KB Output is correct
91 Correct 225 ms 440656 KB Output is correct
92 Correct 262 ms 440400 KB Output is correct
93 Correct 285 ms 440912 KB Output is correct
94 Correct 315 ms 440400 KB Output is correct
95 Correct 319 ms 440596 KB Output is correct
96 Correct 310 ms 440524 KB Output is correct
97 Correct 292 ms 440656 KB Output is correct
98 Correct 288 ms 441180 KB Output is correct
99 Correct 259 ms 440572 KB Output is correct
100 Correct 195 ms 440748 KB Output is correct
101 Correct 213 ms 440692 KB Output is correct
102 Correct 130 ms 440912 KB Output is correct
103 Correct 436 ms 440400 KB Output is correct
104 Correct 342 ms 440404 KB Output is correct
105 Correct 491 ms 440924 KB Output is correct
106 Correct 425 ms 441204 KB Output is correct
107 Correct 474 ms 440400 KB Output is correct
108 Correct 347 ms 440400 KB Output is correct
109 Correct 479 ms 440912 KB Output is correct
110 Correct 394 ms 440924 KB Output is correct
111 Correct 520 ms 440876 KB Output is correct
112 Correct 409 ms 440812 KB Output is correct
113 Correct 291 ms 440656 KB Output is correct
114 Correct 280 ms 440912 KB Output is correct
115 Correct 350 ms 440400 KB Output is correct
116 Correct 350 ms 440812 KB Output is correct
117 Correct 283 ms 441208 KB Output is correct
118 Correct 371 ms 440656 KB Output is correct
119 Correct 290 ms 440712 KB Output is correct
120 Correct 342 ms 440660 KB Output is correct
121 Correct 358 ms 440840 KB Output is correct
122 Correct 366 ms 440668 KB Output is correct
123 Correct 463 ms 440656 KB Output is correct
124 Correct 394 ms 440756 KB Output is correct
125 Correct 472 ms 440912 KB Output is correct
126 Correct 434 ms 440816 KB Output is correct
127 Correct 345 ms 440912 KB Output is correct
128 Correct 296 ms 440656 KB Output is correct
129 Correct 310 ms 440676 KB Output is correct
130 Correct 295 ms 440908 KB Output is correct