oj.uz

Submission #544510

# Submission time Handle Problem Language Result Execution time Memory
544510 2022-04-02T07:03:20 Z model_code Fish 2 (JOI22_fish2) C++17
100 / 100
 1784 ms 183948 KB 
#include <bits/stdc++.h>
using namespace std;

#define INF 1000000007
using ll=long long;

struct interval{
    int l,r;
    bool operator<(const interval p)const{
        return r-l<p.r-p.l;
    }
};

struct SEG_interval{
    stack<interval>seg[1<<18];
    void add(int a,vector<interval>x){
        sort(x.begin(),x.end());
        reverse(x.begin(),x.end());
        int l=a,r=a;
        a+=(1<<17)-1;
        while(1){
            while(x.size()>0&&l<=x.back().l&&x.back().r<=r){
                seg[a].push(x.back());
                x.pop_back();
            }
            if(a==0)break;
            if(a%2==0)l-=(r-l+1);
            else r+=(r-l+1);
            a=(a-1)/2;
        }
    }
    vector<interval> erase(int a){
        vector<interval>res;
        int x=a;
        a+=(1<<17)-1;
        while(1){
            while(!seg[a].empty()&&seg[a].top().l<=x&&x<=seg[a].top().r){
                res.push_back(seg[a].top());
                seg[a].pop();
            }
            if(a==0)break;
            a=(a-1)/2;
        }
        return res;
    }
}seg_interval;

struct Node{
    int mi,cnt;
    static Node merge(const Node a,const Node b){
        Node res;
        res.mi=min(a.mi,b.mi);
        res.cnt=0;
        if(res.mi==a.mi)res.cnt+=a.cnt;
        if(res.mi==b.mi)res.cnt+=b.cnt;
        return res;
    }
};

struct SEG_count{
    Node seg[1<<18];
    int la[1<<18];
    SEG_count(){
        for(int i=(1<<18)-1;i>=0;i--){
            la[i]=0;
            if(i>=(1<<17)-1)seg[i].mi=0,seg[i].cnt=1;
            else seg[i]=Node::merge(seg[i*2+1],seg[i*2+2]);
        }
    }
    void eval(int a){
        seg[a].mi+=la[a];
        if(a<(1<<17)-1){
            la[a*2+1]+=la[a];
            la[a*2+2]+=la[a];
        }
        la[a]=0;
    }
    void add(int a,int b,int x,int k=0,int l=0,int r=(1<<17)-1){
        eval(k);
        if(b<l||r<a)return;
        if(a<=l&&r<=b){
            la[k]+=x;
            eval(k);
            return;
        }
        add(a,b,x,k*2+1,l,(l+r-1)/2);
        add(a,b,x,k*2+2,(l+r+1)/2,r);
        seg[k]=Node::merge(seg[k*2+1],seg[k*2+2]);
    }
    Node query(int a,int b,int k=0,int l=0,int r=(1<<17)-1){
        eval(k);
        if(b<l||r<a)return Node{INF,1};
        if(a<=l&&r<=b)return seg[k];
        return Node::merge(query(a,b,k*2+1,l,(l+r-1)/2),query(a,b,k*2+2,(l+r+1)/2,r));
    }
}seg_count;

struct SEG_others{
    ll sum[1<<18];
    int ma[1<<18];
    SEG_others(){
        for(int i=0;i<1<<18;i++)sum[i]=0,ma[i]=0;
    }
    void update(int a,int x){
        a+=(1<<17)-1;
        sum[a]=x;
        ma[a]=x;
        while(a>0){
            a=(a-1)/2;
            sum[a]=sum[a*2+1]+sum[a*2+2];
            ma[a]=max(ma[a*2+1],ma[a*2+2]);
        }
    }
    ll query_sum(int a,int b,int k=0,int l=0,int r=(1<<17)-1){
        if(b<l||r<a)return 0;
        if(a<=l&&r<=b)return sum[k];
        return query_sum(a,b,k*2+1,l,(l+r-1)/2)+query_sum(a,b,k*2+2,(l+r+1)/2,r);
    }
    int leftest(int a,int x,int k=0,int l=0,int r=(1<<17)-1){
        if(r<a||ma[k]<=x)return -1;
        if(l==r)return l;
        if(ma[k*2+1]>x){
            int res=leftest(a,x,k*2+1,l,(l+r-1)/2);
            if(res!=-1)return res;
        }
        return leftest(a,x,k*2+2,(l+r+1)/2,r);
    }
    int rightest(int a,int x,int k=0,int l=0,int r=(1<<17)-1){
        if(a<l||ma[k]<=x)return -1;
        if(l==r)return l;
        if(ma[k*2+2]>x){
            int res=rightest(a,x,k*2+2,(l+r+1)/2,r);
            if(res!=-1)return res;
        }
        return rightest(a,x,k*2+1,l,(l+r-1)/2);
    }
}seg_others;

int n,A[100005];

vector<pair<int,ll>>right_cand(int a){
    vector<pair<int,ll>>res;
    ll s=A[a];
    while(a<n){
        a++;
        int nxt=seg_others.leftest(a,s);
        if(nxt==-1)break;
        res.push_back(make_pair(nxt,seg_others.query_sum(0,nxt)));
        s+=A[nxt];
        a=nxt;
    }
    return res;
}

vector<pair<int,ll>>left_cand(int a){
    vector<pair<int,ll>>res;
    ll s=A[a];
    while(a>1){
        a--;
        int nxt=seg_others.rightest(a,s);
        if(nxt==-1)break;
        res.push_back(make_pair(nxt,seg_others.query_sum(0,nxt)));
        s+=A[nxt];
        a=nxt;
    }
    return res;
}

void update(int a,int x){
    for(int i=-1;i<=1;i++){
        vector<interval>del=seg_interval.erase(a+i);
        for(auto j:del)seg_count.add(j.l,j.r,-1);
    }
    A[a]=x;
    seg_others.update(a,x);
    vector<pair<int,ll>>right=right_cand(a+1);
    right.push_back(make_pair(a,seg_others.query_sum(0,a)));
    right.push_back(make_pair(a+1,seg_others.query_sum(0,a+1)));
    vector<pair<int,ll>>left=left_cand(a-1);
    left.push_back(make_pair(a,seg_others.query_sum(0,a)));
    left.push_back(make_pair(a-1,seg_others.query_sum(0,a-1)));
    vector<interval>_bad,bad,bad_;
    for(auto i:left){
        for(auto j:right){
            int l=i.first,r=j.first;
            if(l>=r-1)continue;
            ll s=j.second-A[r]-i.second;
            if(s<A[l]&&s<A[r]){
                l++,r--;
                seg_count.add(l,r,1);
                if(l<=a&&a<=r)bad.push_back(interval{l,r});
                else if(l<=a-1&&a-1<=r)_bad.push_back(interval{l,r});
                else bad_.push_back(interval{l,r});
            }
        }
    }
    seg_interval.add(a-1,_bad);
    seg_interval.add(a+1,bad_);
    seg_interval.add(a,bad);
}

int query(int l,int r){
    ll l_sum=seg_others.query_sum(0,l-1);
    vector<pair<int,ll>>right=right_cand(l);
    for(auto i:right){
        if(i.second-l_sum-A[i.first]<A[i.first]&&i.first<=r)l=max(l,i.first);
    }
    ll r_sum=seg_others.query_sum(0,r);
    vector<pair<int,ll>>left=left_cand(r);
    for(auto i:left){
        if(r_sum-i.second<A[i.first]&&i.first>=l)r=min(r,i.first);
    }
    return seg_count.query(l,r).cnt;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>A[i];
        update(i,A[i]);
    }
    int q;
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int a,x;
            cin>>a>>x;
            update(a,x);
        }else{
            int l,r;
            cin>>l>>r;
            cout<<query(l,r)<<endl;
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 182808 KB Output is correct
2 Correct 127 ms 182856 KB Output is correct
3 Correct 116 ms 182860 KB Output is correct
4 Correct 128 ms 182988 KB Output is correct
5 Correct 124 ms 182804 KB Output is correct
6 Correct 127 ms 182900 KB Output is correct
7 Correct 140 ms 182812 KB Output is correct
8 Correct 135 ms 182872 KB Output is correct
9 Correct 147 ms 182840 KB Output is correct
10 Correct 144 ms 182904 KB Output is correct
11 Correct 131 ms 182900 KB Output is correct
12 Correct 140 ms 182880 KB Output is correct
13 Correct 120 ms 182896 KB Output is correct
14 Correct 130 ms 182792 KB Output is correct
15 Correct 124 ms 182888 KB Output is correct
16 Correct 115 ms 182860 KB Output is correct
17 Correct 133 ms 182864 KB Output is correct
18 Correct 119 ms 182800 KB Output is correct
19 Correct 119 ms 182900 KB Output is correct
20 Correct 125 ms 182884 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 182904 KB Output is correct
2 Correct 334 ms 183256 KB Output is correct
3 Correct 380 ms 183288 KB Output is correct
4 Correct 348 ms 183284 KB Output is correct
5 Correct 367 ms 183220 KB Output is correct
6 Correct 316 ms 183292 KB Output is correct
7 Correct 420 ms 183300 KB Output is correct
8 Correct 319 ms 183184 KB Output is correct
9 Correct 405 ms 183260 KB Output is correct
10 Correct 472 ms 183496 KB Output is correct
11 Correct 503 ms 183304 KB Output is correct
12 Correct 331 ms 183220 KB Output is correct
13 Correct 322 ms 183244 KB Output is correct
14 Correct 347 ms 183384 KB Output is correct
15 Correct 330 ms 183204 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 182808 KB Output is correct
2 Correct 127 ms 182856 KB Output is correct
3 Correct 116 ms 182860 KB Output is correct
4 Correct 128 ms 182988 KB Output is correct
5 Correct 124 ms 182804 KB Output is correct
6 Correct 127 ms 182900 KB Output is correct
7 Correct 140 ms 182812 KB Output is correct
8 Correct 135 ms 182872 KB Output is correct
9 Correct 147 ms 182840 KB Output is correct
10 Correct 144 ms 182904 KB Output is correct
11 Correct 131 ms 182900 KB Output is correct
12 Correct 140 ms 182880 KB Output is correct
13 Correct 120 ms 182896 KB Output is correct
14 Correct 130 ms 182792 KB Output is correct
15 Correct 124 ms 182888 KB Output is correct
16 Correct 115 ms 182860 KB Output is correct
17 Correct 133 ms 182864 KB Output is correct
18 Correct 119 ms 182800 KB Output is correct
19 Correct 119 ms 182900 KB Output is correct
20 Correct 125 ms 182884 KB Output is correct
21 Correct 111 ms 182904 KB Output is correct
22 Correct 334 ms 183256 KB Output is correct
23 Correct 380 ms 183288 KB Output is correct
24 Correct 348 ms 183284 KB Output is correct
25 Correct 367 ms 183220 KB Output is correct
26 Correct 316 ms 183292 KB Output is correct
27 Correct 420 ms 183300 KB Output is correct
28 Correct 319 ms 183184 KB Output is correct
29 Correct 405 ms 183260 KB Output is correct
30 Correct 472 ms 183496 KB Output is correct
31 Correct 503 ms 183304 KB Output is correct
32 Correct 331 ms 183220 KB Output is correct
33 Correct 322 ms 183244 KB Output is correct
34 Correct 347 ms 183384 KB Output is correct
35 Correct 330 ms 183204 KB Output is correct
36 Correct 338 ms 183412 KB Output is correct
37 Correct 396 ms 183244 KB Output is correct
38 Correct 399 ms 183300 KB Output is correct
39 Correct 337 ms 183248 KB Output is correct
40 Correct 384 ms 183284 KB Output is correct
41 Correct 324 ms 183244 KB Output is correct
42 Correct 323 ms 183196 KB Output is correct
43 Correct 458 ms 183308 KB Output is correct
44 Correct 412 ms 183244 KB Output is correct
45 Correct 486 ms 183292 KB Output is correct
46 Correct 484 ms 183296 KB Output is correct
47 Correct 494 ms 183236 KB Output is correct
48 Correct 338 ms 183392 KB Output is correct
49 Correct 311 ms 183264 KB Output is correct
50 Correct 347 ms 183244 KB Output is correct
51 Correct 349 ms 183220 KB Output is correct
52 Correct 343 ms 183224 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 182904 KB Output is correct
2 Correct 334 ms 183256 KB Output is correct
3 Correct 380 ms 183288 KB Output is correct
4 Correct 348 ms 183284 KB Output is correct
5 Correct 367 ms 183220 KB Output is correct
6 Correct 316 ms 183292 KB Output is correct
7 Correct 420 ms 183300 KB Output is correct
8 Correct 319 ms 183184 KB Output is correct
9 Correct 405 ms 183260 KB Output is correct
10 Correct 472 ms 183496 KB Output is correct
11 Correct 503 ms 183304 KB Output is correct
12 Correct 331 ms 183220 KB Output is correct
13 Correct 322 ms 183244 KB Output is correct
14 Correct 347 ms 183384 KB Output is correct
15 Correct 330 ms 183204 KB Output is correct
16 Correct 114 ms 182848 KB Output is correct
17 Correct 1254 ms 183552 KB Output is correct
18 Correct 1106 ms 183704 KB Output is correct
19 Correct 1241 ms 183620 KB Output is correct
20 Correct 1266 ms 183616 KB Output is correct
21 Correct 1221 ms 183756 KB Output is correct
22 Correct 1095 ms 183740 KB Output is correct
23 Correct 1146 ms 183780 KB Output is correct
24 Correct 1350 ms 183576 KB Output is correct
25 Correct 1224 ms 183596 KB Output is correct
26 Correct 1307 ms 183948 KB Output is correct
27 Correct 753 ms 183816 KB Output is correct
28 Correct 735 ms 183852 KB Output is correct
29 Correct 769 ms 183832 KB Output is correct
30 Correct 1264 ms 183648 KB Output is correct
31 Correct 1250 ms 183492 KB Output is correct
32 Correct 1631 ms 183544 KB Output is correct
33 Correct 1088 ms 183776 KB Output is correct
34 Correct 1647 ms 183668 KB Output is correct
35 Correct 1283 ms 183488 KB Output is correct
36 Correct 1504 ms 183688 KB Output is correct
37 Correct 827 ms 183516 KB Output is correct
38 Correct 770 ms 183592 KB Output is correct
39 Correct 865 ms 183872 KB Output is correct
40 Correct 806 ms 183932 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 182904 KB Output is correct
2 Correct 334 ms 183256 KB Output is correct
3 Correct 380 ms 183288 KB Output is correct
4 Correct 348 ms 183284 KB Output is correct
5 Correct 367 ms 183220 KB Output is correct
6 Correct 316 ms 183292 KB Output is correct
7 Correct 420 ms 183300 KB Output is correct
8 Correct 319 ms 183184 KB Output is correct
9 Correct 405 ms 183260 KB Output is correct
10 Correct 472 ms 183496 KB Output is correct
11 Correct 503 ms 183304 KB Output is correct
12 Correct 331 ms 183220 KB Output is correct
13 Correct 322 ms 183244 KB Output is correct
14 Correct 347 ms 183384 KB Output is correct
15 Correct 330 ms 183204 KB Output is correct
16 Correct 118 ms 182860 KB Output is correct
17 Correct 1411 ms 183324 KB Output is correct
18 Correct 1321 ms 183472 KB Output is correct
19 Correct 1398 ms 183560 KB Output is correct
20 Correct 1196 ms 183428 KB Output is correct
21 Correct 1784 ms 183568 KB Output is correct
22 Correct 1331 ms 183312 KB Output is correct
23 Correct 1583 ms 183340 KB Output is correct
24 Correct 1283 ms 183420 KB Output is correct
25 Correct 1448 ms 183460 KB Output is correct
26 Correct 773 ms 183680 KB Output is correct
27 Correct 833 ms 183292 KB Output is correct
28 Correct 1075 ms 183648 KB Output is correct
29 Correct 786 ms 183476 KB Output is correct
30 Correct 807 ms 183360 KB Output is correct
31 Correct 1179 ms 183368 KB Output is correct
32 Correct 1365 ms 183476 KB Output is correct
33 Correct 1057 ms 183352 KB Output is correct
34 Correct 1297 ms 183548 KB Output is correct
35 Correct 1025 ms 183464 KB Output is correct
36 Correct 1298 ms 183480 KB Output is correct
37 Correct 1085 ms 183456 KB Output is correct
38 Correct 978 ms 183680 KB Output is correct
39 Correct 919 ms 183600 KB Output is correct
40 Correct 823 ms 183756 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 182808 KB Output is correct
2 Correct 127 ms 182856 KB Output is correct
3 Correct 116 ms 182860 KB Output is correct
4 Correct 128 ms 182988 KB Output is correct
5 Correct 124 ms 182804 KB Output is correct
6 Correct 127 ms 182900 KB Output is correct
7 Correct 140 ms 182812 KB Output is correct
8 Correct 135 ms 182872 KB Output is correct
9 Correct 147 ms 182840 KB Output is correct
10 Correct 144 ms 182904 KB Output is correct
11 Correct 131 ms 182900 KB Output is correct
12 Correct 140 ms 182880 KB Output is correct
13 Correct 120 ms 182896 KB Output is correct
14 Correct 130 ms 182792 KB Output is correct
15 Correct 124 ms 182888 KB Output is correct
16 Correct 115 ms 182860 KB Output is correct
17 Correct 133 ms 182864 KB Output is correct
18 Correct 119 ms 182800 KB Output is correct
19 Correct 119 ms 182900 KB Output is correct
20 Correct 125 ms 182884 KB Output is correct
21 Correct 111 ms 182904 KB Output is correct
22 Correct 334 ms 183256 KB Output is correct
23 Correct 380 ms 183288 KB Output is correct
24 Correct 348 ms 183284 KB Output is correct
25 Correct 367 ms 183220 KB Output is correct
26 Correct 316 ms 183292 KB Output is correct
27 Correct 420 ms 183300 KB Output is correct
28 Correct 319 ms 183184 KB Output is correct
29 Correct 405 ms 183260 KB Output is correct
30 Correct 472 ms 183496 KB Output is correct
31 Correct 503 ms 183304 KB Output is correct
32 Correct 331 ms 183220 KB Output is correct
33 Correct 322 ms 183244 KB Output is correct
34 Correct 347 ms 183384 KB Output is correct
35 Correct 330 ms 183204 KB Output is correct
36 Correct 338 ms 183412 KB Output is correct
37 Correct 396 ms 183244 KB Output is correct
38 Correct 399 ms 183300 KB Output is correct
39 Correct 337 ms 183248 KB Output is correct
40 Correct 384 ms 183284 KB Output is correct
41 Correct 324 ms 183244 KB Output is correct
42 Correct 323 ms 183196 KB Output is correct
43 Correct 458 ms 183308 KB Output is correct
44 Correct 412 ms 183244 KB Output is correct
45 Correct 486 ms 183292 KB Output is correct
46 Correct 484 ms 183296 KB Output is correct
47 Correct 494 ms 183236 KB Output is correct
48 Correct 338 ms 183392 KB Output is correct
49 Correct 311 ms 183264 KB Output is correct
50 Correct 347 ms 183244 KB Output is correct
51 Correct 349 ms 183220 KB Output is correct
52 Correct 343 ms 183224 KB Output is correct
53 Correct 114 ms 182848 KB Output is correct
54 Correct 1254 ms 183552 KB Output is correct
55 Correct 1106 ms 183704 KB Output is correct
56 Correct 1241 ms 183620 KB Output is correct
57 Correct 1266 ms 183616 KB Output is correct
58 Correct 1221 ms 183756 KB Output is correct
59 Correct 1095 ms 183740 KB Output is correct
60 Correct 1146 ms 183780 KB Output is correct
61 Correct 1350 ms 183576 KB Output is correct
62 Correct 1224 ms 183596 KB Output is correct
63 Correct 1307 ms 183948 KB Output is correct
64 Correct 753 ms 183816 KB Output is correct
65 Correct 735 ms 183852 KB Output is correct
66 Correct 769 ms 183832 KB Output is correct
67 Correct 1264 ms 183648 KB Output is correct
68 Correct 1250 ms 183492 KB Output is correct
69 Correct 1631 ms 183544 KB Output is correct
70 Correct 1088 ms 183776 KB Output is correct
71 Correct 1647 ms 183668 KB Output is correct
72 Correct 1283 ms 183488 KB Output is correct
73 Correct 1504 ms 183688 KB Output is correct
74 Correct 827 ms 183516 KB Output is correct
75 Correct 770 ms 183592 KB Output is correct
76 Correct 865 ms 183872 KB Output is correct
77 Correct 806 ms 183932 KB Output is correct
78 Correct 118 ms 182860 KB Output is correct
79 Correct 1411 ms 183324 KB Output is correct
80 Correct 1321 ms 183472 KB Output is correct
81 Correct 1398 ms 183560 KB Output is correct
82 Correct 1196 ms 183428 KB Output is correct
83 Correct 1784 ms 183568 KB Output is correct
84 Correct 1331 ms 183312 KB Output is correct
85 Correct 1583 ms 183340 KB Output is correct
86 Correct 1283 ms 183420 KB Output is correct
87 Correct 1448 ms 183460 KB Output is correct
88 Correct 773 ms 183680 KB Output is correct
89 Correct 833 ms 183292 KB Output is correct
90 Correct 1075 ms 183648 KB Output is correct
91 Correct 786 ms 183476 KB Output is correct
92 Correct 807 ms 183360 KB Output is correct
93 Correct 1179 ms 183368 KB Output is correct
94 Correct 1365 ms 183476 KB Output is correct
95 Correct 1057 ms 183352 KB Output is correct
96 Correct 1297 ms 183548 KB Output is correct
97 Correct 1025 ms 183464 KB Output is correct
98 Correct 1298 ms 183480 KB Output is correct
99 Correct 1085 ms 183456 KB Output is correct
100 Correct 978 ms 183680 KB Output is correct
101 Correct 919 ms 183600 KB Output is correct
102 Correct 823 ms 183756 KB Output is correct
103 Correct 1320 ms 183440 KB Output is correct
104 Correct 1247 ms 183436 KB Output is correct
105 Correct 1395 ms 183760 KB Output is correct
106 Correct 1182 ms 183716 KB Output is correct
107 Correct 1646 ms 183536 KB Output is correct
108 Correct 1241 ms 183448 KB Output is correct
109 Correct 1335 ms 183592 KB Output is correct
110 Correct 1223 ms 183568 KB Output is correct
111 Correct 1382 ms 183676 KB Output is correct
112 Correct 1197 ms 183844 KB Output is correct
113 Correct 851 ms 183560 KB Output is correct
114 Correct 784 ms 183732 KB Output is correct
115 Correct 1216 ms 183320 KB Output is correct
116 Correct 1151 ms 183612 KB Output is correct
117 Correct 784 ms 183756 KB Output is correct
118 Correct 1121 ms 183768 KB Output is correct
119 Correct 860 ms 183452 KB Output is correct
120 Correct 1191 ms 183588 KB Output is correct
121 Correct 1117 ms 183828 KB Output is correct
122 Correct 1369 ms 183352 KB Output is correct
123 Correct 1079 ms 183608 KB Output is correct
124 Correct 1243 ms 183628 KB Output is correct
125 Correct 1252 ms 183508 KB Output is correct
126 Correct 1295 ms 183688 KB Output is correct
127 Correct 1139 ms 183504 KB Output is correct
128 Correct 901 ms 183548 KB Output is correct
129 Correct 978 ms 183564 KB Output is correct
130 Correct 865 ms 183672 KB Output is correct