oj.uz

Submission #870858

# Submission time Handle Problem Language Result Execution time Memory
870858 2023-11-09T10:13:12 Z willychan Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 32284 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+1,a.r-1,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) {
//				cout<<"remove "<<cur.l<<" "<<cur.r<<"->"<<ind<<"\n";
                segtree.modify(1,cur.l+1,cur.r-1,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);
    }
} 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);
    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){
				inttree.insert(range(pl.first,pr.first),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(1,n),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++;
			MainUpdate(x,y);
        } else {
            int l,r;
            cin>>l>>r;
            l++;
            r++;
			ll rog = A[r+1];
			ll log = A[l-1];
			MainUpdate(r+1,1e16);
			MainUpdate(l-1,1e16);
            pair<int,int> ans = segtree.query(1,l,r,1,n);
           cout<<ans.second<<"\n";
			MainUpdate(r+1,rog);
			MainUpdate(l-1,log);
        }
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 5 ms 608 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 386 ms 29268 KB Output is correct
3 Correct 491 ms 29268 KB Output is correct
4 Correct 327 ms 29316 KB Output is correct
5 Correct 494 ms 29392 KB Output is correct
6 Correct 314 ms 29652 KB Output is correct
7 Correct 587 ms 28844 KB Output is correct
8 Correct 345 ms 29780 KB Output is correct
9 Correct 573 ms 28624 KB Output is correct
10 Correct 823 ms 28888 KB Output is correct
11 Correct 989 ms 28868 KB Output is correct
12 Correct 410 ms 29124 KB Output is correct
13 Correct 391 ms 29012 KB Output is correct
14 Correct 372 ms 29480 KB Output is correct
15 Correct 351 ms 29592 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 5 ms 608 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 386 ms 29268 KB Output is correct
3 Correct 491 ms 29268 KB Output is correct
4 Correct 327 ms 29316 KB Output is correct
5 Correct 494 ms 29392 KB Output is correct
6 Correct 314 ms 29652 KB Output is correct
7 Correct 587 ms 28844 KB Output is correct
8 Correct 345 ms 29780 KB Output is correct
9 Correct 573 ms 28624 KB Output is correct
10 Correct 823 ms 28888 KB Output is correct
11 Correct 989 ms 28868 KB Output is correct
12 Correct 410 ms 29124 KB Output is correct
13 Correct 391 ms 29012 KB Output is correct
14 Correct 372 ms 29480 KB Output is correct
15 Correct 351 ms 29592 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Execution timed out 4062 ms 32284 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 386 ms 29268 KB Output is correct
3 Correct 491 ms 29268 KB Output is correct
4 Correct 327 ms 29316 KB Output is correct
5 Correct 494 ms 29392 KB Output is correct
6 Correct 314 ms 29652 KB Output is correct
7 Correct 587 ms 28844 KB Output is correct
8 Correct 345 ms 29780 KB Output is correct
9 Correct 573 ms 28624 KB Output is correct
10 Correct 823 ms 28888 KB Output is correct
11 Correct 989 ms 28868 KB Output is correct
12 Correct 410 ms 29124 KB Output is correct
13 Correct 391 ms 29012 KB Output is correct
14 Correct 372 ms 29480 KB Output is correct
15 Correct 351 ms 29592 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Incorrect 1251 ms 30588 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 5 ms 608 KB Output isn't correct
6 Halted 0 ms 0 KB -