oj.uz

Submission #870872

# Submission time Handle Problem Language Result Execution time Memory
870872 2023-11-09T11:35:58 Z willychan Fish 2 (JOI22_fish2) C++14
60 / 100
 4000 ms 33316 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds

vector<ll> A;
struct SegTree {
    vector<pair<int,int> > arr;
    vector<int> tag;
    int n;
	void built(int ind,int L,int R){
		arr[ind].second = (R-L+1); 
		if(L==R) return;
		int M = (L+R)/2;
		built(2*ind,L,M);
		built(2*ind+1,M+1,R);
	}
    void init(int _n) {
        n =_n;
        arr.resize(4*n);
        tag.resize(4*n); 
		built(1,1,n);
	} 
	void push(int ind) {
        if(2*ind+1>4*n) return;
        if(tag[ind]) {
            arr[2*ind].first+=tag[ind];
            arr[2*ind+1].first+=tag[ind];
            tag[2*ind]+=tag[ind];
            tag[2*ind+1]+=tag[ind];
            tag[ind]=0;
        }
    }
    inline pair<int,int> merge(const pair<int,int> a,const pair<int,int> b) {
        if(a.first!=b.first) return min(a,b);
        return {a.first,a.second+b.second};
    }
    pair<int,int> query(int ind,int l,int r,int L,int R) {
        if(l==L && r==R) {
            return arr[ind];
        }
        push(ind);
        int M = (L+R)/2;
        if(r<=M) return query(2*ind,l,r,L,M);
        if(l>M) return query(2*ind+1,l,r,M+1,R);
        return merge(query(2*ind,l,M,L,M),query(2*ind+1,M+1,r,M+1,R));
    }
    void modify(int ind,int l,int r,int L,int R,int v) {
		//cout<<l<<" "<<r<<"~"<<L<<" "<<R<<"safd"<<endl;
        if(l==L && r==R) {
            arr[ind].first+=v;
            tag[ind]+=v;
            return ;
        }
        push(ind);
        int M = (L+R)/2;
        if(r<=M) modify(2*ind,l,r,L,M,v);
        else if(l>M) modify(2*ind+1,l,r,M+1,R,v);
        else {
            modify(2*ind,l,M,L,M,v);
            modify(2*ind+1,M+1,r,M+1,R,v);
        }
        arr[ind] = merge(arr[2*ind],arr[2*ind+1]);
    }

} segtree;

struct range {
    int l,r;
    range(int _l,int _r) {
        l = _l;
        r = _r;
    }
    bool operator<(const range &rhs) const {
        return (r-l)<(rhs.r-rhs.l);
    }
};
struct IntTree {
    vector<priority_queue<range> > arr;
    int n;
    void init(int _n) {
        n = _n;
        arr.resize(4*n);
    }
    void insert(range a,int ind,int L,int R) {
        int M = (L+R)/2;
        if(a.l<=M && a.r>=M) { 
			//cout<<"insert "<<a.l<<" "<<a.r<<"->"<<ind<<"\n";
            arr[ind].push(a);
            segtree.modify(1,a.l,a.r,1,n,1);
            return;
        }
        if(a.r<=M) insert(a,2*ind,L,M);
        else insert(a,2*ind+1,M+1,R);
    }
    void remove(int x,int ind,int L,int R) {
        while(arr[ind].size()) {
            range cur = arr[ind].top();
            if(cur.l<=x && cur.r>=x) {
                segtree.modify(1,cur.l,cur.r,1,n,-1);
                arr[ind].pop();
            } else {
                break;
            }
        }
        int M = (L+R)/2;
		if(x==M) return;
        if(x<M) remove(x,2*ind,L,M);
        if(x>M) remove(x,2*ind+1,M+1,R);
    }
	void out(int ind,int L,int R){
		auto pq = arr[ind];
		while(pq.size()){
//			cout<<pq.top().l<<" "<<pq.top().r<<"->"<<ind<<"k\n";
			pq.pop();
		}
		if(L==R) return;
		int M = (L+R)/2;
		out(2*ind,L,M);
		out(2*ind+1,M+1,R);
	}
} inttree;

struct SegTree2 {
    vector< pair<ll,ll> > arr;
    // a[i]+A[i]>A[x]
    // 2*a[i]-A[i]>-A[x-1]
    vector<ll> tag;
    int n;
    void init(int _n) {
        n = _n;
        arr.resize(4*n);
        tag.resize(4*n);
    }
    void apply(int ind,ll v) {
        arr[ind].first+=v;
        arr[ind].second-=v;
        tag[ind]+=v;
    }
    void push(int ind) {
        if(2*ind+1>=4*n) return;
        if(tag[ind]) {
            apply(2*ind,tag[ind]);
            apply(2*ind+1,tag[ind]);
            tag[ind]=0;
        }
    }
    ll sum(int ind,int x,int L,int R) {
        if(L==R && L==x) {
            return arr[ind].first-A[x];
        }
        push(ind);
        int M = (L+R)/2;
        if(x<=M) return sum(2*ind,x,L,M);
        if(x>M) return sum(2*ind+1,x,M+1,R);
        assert(1==0);
        return 0;
    }
    void smodify(int ind,int x,int L,int R,ll v) {
        if(L==x && R==x) {
            arr[ind].first+=v;
            arr[ind].second+=2*v;
            return;
        }
        push(ind);
        int M = (L+R)/2;
        if(x<=M) smodify(2*ind,x,L,M,v);
        if(x>M) smodify(2*ind+1,x,M+1,R,v);
        arr[ind] = {max(arr[2*ind].first,arr[2*ind+1].first),max(arr[2*ind].second,arr[2*ind+1].second)};
    }
    void rmodify(int ind,int l,int r,int L,int R,ll v) {
        if(l==L && r==R) {
            apply(ind,v);
            return;
        }
        push(ind);
        int M = (L+R)/2;
        if(r<=M) rmodify(2*ind,l,r,L,M,v);
        else if(l>M)  rmodify(2*ind+1,l,r,M+1,R,v);
        else {
            rmodify(2*ind,l,M,L,M,v);
            rmodify(2*ind+1,M+1,r,M+1,R,v);
        }
        arr[ind] = {max(arr[2*ind].first,arr[2*ind+1].first),max(arr[2*ind].second,arr[2*ind+1].second)};
    }

    void update(int ind,ll v) {
        ll k = v-A[ind];
        smodify(1,ind,1,n,k);
        rmodify(1,ind,n,1,n,k);
        A[ind]=v;
    }
    void getr(int ind,ll v,int x,int L,int R,vector<pair<int,ll> > &ret) {
        if(R<x) return;
        if(arr[ind].second<=v) return;
        if(L==R) {
            ret.push_back({L,arr[ind].second});
            return;
        }
        push(ind);
        int M =(L+R)/2;
        getr(2*ind,v,x,L,M,ret);
        getr(2*ind+1,v,x,M+1,R,ret);
    }
    void getl(int ind,ll v,int x,int L,int R,vector<pair<int,ll> > &ret) {
        if(L>x)	 return;
        if(arr[ind].first<=v) return;
        if(L==R) {
            ret.push_back({L,arr[ind].first});
            return;
        }
        push(ind);
        int M = (L+R)/2;
        getl(2*ind,v,x,L,M,ret);
        getl(2*ind+1,v,x,M+1,R,ret);
    }
} segtree2;

int n;
void MainUpdate(int ind,ll v) {
    inttree.remove(ind,1,1,n);
	inttree.remove(ind-1,1,1,n);
	inttree.remove(ind+1,1,1,n);
    segtree2.update(ind,v);
    vector<pair<int,ll> > rcan;
    vector<pair<int,ll> > lcan;
    ll Ax = segtree2.sum(1,ind,1,n);
    segtree2.getr(1,-(Ax),ind,1,n,rcan);
    segtree2.getl(1,Ax-A[ind],ind,1,n,lcan);
    // a[i]+A[i]>A[x-1]
    // 2*a[i]-A[i]>-A[x]
    for(auto pr : rcan) {
        for(auto pl : lcan) { if(pr.first-1<pl.first+1) continue;
            ll sumbet = (A[pr.first]-pr.second)-(pl.second-A[pl.first]);
            if(A[pr.first]>sumbet && A[pl.first]>sumbet){
				//if(ind==4) cout<<pl.first<<" "<<pr.first<<"gg\n";
				inttree.insert(range(pl.first+1,pr.first-1),1,1,n);
			}
        }
    }

}

int main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    n+=2;
    segtree.init(n);
    inttree.init(n);
    segtree2.init(n);
    A.resize(n+1);
    inttree.insert(range(2,n-1),1,1,n);
    segtree2.update(1,1e16);
    segtree2.update(n,1e16);
    for(int i=2; i<n; i++) {
        ll v;
        cin>>v;
		MainUpdate(i,v);
    }
    int q;
    cin>>q;
    while(q--) {
        int t;
        cin>>t;
        if(t==1) {
            int x,y;
            cin>>x>>y;
            x++;
//			cout<<"t\n";
			MainUpdate(x,y);
        } else {
            int l,r;
            cin>>l>>r;
            l++;
            r++;
			ll rog = A[r+1];
			ll log = A[l-1];
			if(r+1<n) MainUpdate(r+1,1e16);
			if(l-1>1) MainUpdate(l-1,1e16);
            pair<int,int> ans = segtree.query(1,l,r,1,n);
           cout<<ans.second<<"\n";
			if(r+1<n) MainUpdate(r+1,rog);
			if(l-1>1) MainUpdate(l-1,log);
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 608 KB Output is correct
6 Correct 9 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 12 ms 464 KB Output is correct
9 Correct 9 ms 608 KB Output is correct
10 Correct 4 ms 600 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 7 ms 604 KB Output is correct
16 Correct 8 ms 604 KB Output is correct
17 Correct 4 ms 604 KB Output is correct
18 Correct 7 ms 612 KB Output is correct
19 Correct 4 ms 600 KB Output is correct
20 Correct 5 ms 604 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 347 ms 29364 KB Output is correct
3 Correct 526 ms 29524 KB Output is correct
4 Correct 346 ms 29332 KB Output is correct
5 Correct 492 ms 29268 KB Output is correct
6 Correct 324 ms 30032 KB Output is correct
7 Correct 551 ms 28752 KB Output is correct
8 Correct 327 ms 30188 KB Output is correct
9 Correct 559 ms 28756 KB Output is correct
10 Correct 825 ms 28936 KB Output is correct
11 Correct 970 ms 28780 KB Output is correct
12 Correct 423 ms 29008 KB Output is correct
13 Correct 411 ms 29268 KB Output is correct
14 Correct 359 ms 30032 KB Output is correct
15 Correct 388 ms 30080 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 608 KB Output is correct
6 Correct 9 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 12 ms 464 KB Output is correct
9 Correct 9 ms 608 KB Output is correct
10 Correct 4 ms 600 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 7 ms 604 KB Output is correct
16 Correct 8 ms 604 KB Output is correct
17 Correct 4 ms 604 KB Output is correct
18 Correct 7 ms 612 KB Output is correct
19 Correct 4 ms 600 KB Output is correct
20 Correct 5 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 347 ms 29364 KB Output is correct
23 Correct 526 ms 29524 KB Output is correct
24 Correct 346 ms 29332 KB Output is correct
25 Correct 492 ms 29268 KB Output is correct
26 Correct 324 ms 30032 KB Output is correct
27 Correct 551 ms 28752 KB Output is correct
28 Correct 327 ms 30188 KB Output is correct
29 Correct 559 ms 28756 KB Output is correct
30 Correct 825 ms 28936 KB Output is correct
31 Correct 970 ms 28780 KB Output is correct
32 Correct 423 ms 29008 KB Output is correct
33 Correct 411 ms 29268 KB Output is correct
34 Correct 359 ms 30032 KB Output is correct
35 Correct 388 ms 30080 KB Output is correct
36 Correct 377 ms 29772 KB Output is correct
37 Correct 565 ms 29384 KB Output is correct
38 Correct 546 ms 29316 KB Output is correct
39 Correct 359 ms 29708 KB Output is correct
40 Correct 531 ms 29524 KB Output is correct
41 Correct 339 ms 30232 KB Output is correct
42 Correct 337 ms 30072 KB Output is correct
43 Correct 588 ms 28756 KB Output is correct
44 Correct 550 ms 29020 KB Output is correct
45 Correct 912 ms 29136 KB Output is correct
46 Correct 862 ms 29012 KB Output is correct
47 Correct 1012 ms 28500 KB Output is correct
48 Correct 426 ms 29196 KB Output is correct
49 Correct 410 ms 29008 KB Output is correct
50 Correct 387 ms 30436 KB Output is correct
51 Correct 386 ms 29956 KB Output is correct
52 Correct 383 ms 30648 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 347 ms 29364 KB Output is correct
3 Correct 526 ms 29524 KB Output is correct
4 Correct 346 ms 29332 KB Output is correct
5 Correct 492 ms 29268 KB Output is correct
6 Correct 324 ms 30032 KB Output is correct
7 Correct 551 ms 28752 KB Output is correct
8 Correct 327 ms 30188 KB Output is correct
9 Correct 559 ms 28756 KB Output is correct
10 Correct 825 ms 28936 KB Output is correct
11 Correct 970 ms 28780 KB Output is correct
12 Correct 423 ms 29008 KB Output is correct
13 Correct 411 ms 29268 KB Output is correct
14 Correct 359 ms 30032 KB Output is correct
15 Correct 388 ms 30080 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Execution timed out 4080 ms 32712 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 347 ms 29364 KB Output is correct
3 Correct 526 ms 29524 KB Output is correct
4 Correct 346 ms 29332 KB Output is correct
5 Correct 492 ms 29268 KB Output is correct
6 Correct 324 ms 30032 KB Output is correct
7 Correct 551 ms 28752 KB Output is correct
8 Correct 327 ms 30188 KB Output is correct
9 Correct 559 ms 28756 KB Output is correct
10 Correct 825 ms 28936 KB Output is correct
11 Correct 970 ms 28780 KB Output is correct
12 Correct 423 ms 29008 KB Output is correct
13 Correct 411 ms 29268 KB Output is correct
14 Correct 359 ms 30032 KB Output is correct
15 Correct 388 ms 30080 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 988 ms 30804 KB Output is correct
18 Correct 1036 ms 33264 KB Output is correct
19 Correct 998 ms 31044 KB Output is correct
20 Correct 896 ms 32780 KB Output is correct
21 Correct 931 ms 31084 KB Output is correct
22 Correct 1018 ms 33316 KB Output is correct
23 Correct 1065 ms 30684 KB Output is correct
24 Correct 982 ms 32688 KB Output is correct
25 Correct 1016 ms 30552 KB Output is correct
26 Correct 581 ms 32216 KB Output is correct
27 Correct 699 ms 32688 KB Output is correct
28 Correct 896 ms 31776 KB Output is correct
29 Correct 615 ms 32516 KB Output is correct
30 Correct 663 ms 32508 KB Output is correct
31 Correct 1080 ms 32080 KB Output is correct
32 Correct 1469 ms 32440 KB Output is correct
33 Correct 1239 ms 30236 KB Output is correct
34 Correct 1284 ms 32852 KB Output is correct
35 Correct 1052 ms 30160 KB Output is correct
36 Correct 1382 ms 32420 KB Output is correct
37 Correct 825 ms 31336 KB Output is correct
38 Correct 656 ms 31184 KB Output is correct
39 Correct 652 ms 32316 KB Output is correct
40 Correct 499 ms 31824 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 608 KB Output is correct
6 Correct 9 ms 604 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 12 ms 464 KB Output is correct
9 Correct 9 ms 608 KB Output is correct
10 Correct 4 ms 600 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 7 ms 604 KB Output is correct
16 Correct 8 ms 604 KB Output is correct
17 Correct 4 ms 604 KB Output is correct
18 Correct 7 ms 612 KB Output is correct
19 Correct 4 ms 600 KB Output is correct
20 Correct 5 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 347 ms 29364 KB Output is correct
23 Correct 526 ms 29524 KB Output is correct
24 Correct 346 ms 29332 KB Output is correct
25 Correct 492 ms 29268 KB Output is correct
26 Correct 324 ms 30032 KB Output is correct
27 Correct 551 ms 28752 KB Output is correct
28 Correct 327 ms 30188 KB Output is correct
29 Correct 559 ms 28756 KB Output is correct
30 Correct 825 ms 28936 KB Output is correct
31 Correct 970 ms 28780 KB Output is correct
32 Correct 423 ms 29008 KB Output is correct
33 Correct 411 ms 29268 KB Output is correct
34 Correct 359 ms 30032 KB Output is correct
35 Correct 388 ms 30080 KB Output is correct
36 Correct 377 ms 29772 KB Output is correct
37 Correct 565 ms 29384 KB Output is correct
38 Correct 546 ms 29316 KB Output is correct
39 Correct 359 ms 29708 KB Output is correct
40 Correct 531 ms 29524 KB Output is correct
41 Correct 339 ms 30232 KB Output is correct
42 Correct 337 ms 30072 KB Output is correct
43 Correct 588 ms 28756 KB Output is correct
44 Correct 550 ms 29020 KB Output is correct
45 Correct 912 ms 29136 KB Output is correct
46 Correct 862 ms 29012 KB Output is correct
47 Correct 1012 ms 28500 KB Output is correct
48 Correct 426 ms 29196 KB Output is correct
49 Correct 410 ms 29008 KB Output is correct
50 Correct 387 ms 30436 KB Output is correct
51 Correct 386 ms 29956 KB Output is correct
52 Correct 383 ms 30648 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Execution timed out 4080 ms 32712 KB Time limit exceeded
55 Halted 0 ms 0 KB -