Submission #870659

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870659	2023-11-08T17:50:36 Z	Irate	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	438 ms	205684 KB

apple

#include <bits/stdc++.h>
using namespace std;
/*



	NOT MY CODE



*/
const int mxN = (int)2e5+10;
const int INF = (int)1e9+10;
int n, q, a[mxN];
 
struct Vertex{
    int l, r, lazy, sum=0;
    Vertex *le, *ri;
 
    Vertex(int l, int r):l(l),r(r){
        le=ri=nullptr; lazy=INF;
    }
 
    ~Vertex(){
        delete le;
        delete ri;
    }
 
    void extend(){
        if(!le and l!=r){
            int m = (l+r)/2;
            le=new Vertex(l,m);
            ri=new Vertex(m+1,r);
        }
    }
 
    void prop(){
        if(l==r or lazy==INF) return;
        int m = (l+r)/2;
        if(!le) return;
        le->lazy = lazy;
        ri->lazy = lazy;
        le->sum = (m-l+1)*lazy;
        ri->sum = (r-m)*lazy;
        lazy=INF;
    }
 
    void upd(int i, int j, int v){
        if(i>r or j<l or i>j) return;
        if(i<=l and r<=j){
            sum = v*(r-l+1); lazy = v;
            return;
        }
        extend(); prop();
        int m = (l+r)/2;
        if(i<=m) le->upd(i,j,v);
        if(m<j) ri->upd(i,j,v);
        sum=le->sum+ri->sum;
    }
 
    int query(int i, int j){
        if(i>r or j<l or i>j) return 0;
        if(i<=l and r<=j) return sum;
        extend(); prop();
        int m = (l+r)/2;
        int sum = 0;
        if(i<=m) sum+=le->query(i,j);
        if(m<j) sum+=ri->query(i,j);
        return sum;
    }
 
};
 
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> q; int c = 0; Vertex Root(1,INF);
    while(q--){
        int t, x, y; cin >> t >> x >> y; x+=c, y+=c;
        if(t==1){ c = Root.query(x,y); cout << c << "\n"; }
        else Root.upd(x,y,1);
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	10 ms	4956 KB	Output is correct
5	Correct	14 ms	5980 KB	Output is correct
6	Correct	16 ms	5724 KB	Output is correct
7	Correct	13 ms	5976 KB	Output is correct
8	Correct	128 ms	43856 KB	Output is correct
9	Correct	253 ms	75552 KB	Output is correct
10	Correct	259 ms	83776 KB	Output is correct
11	Correct	266 ms	89944 KB	Output is correct
12	Correct	269 ms	92824 KB	Output is correct
13	Correct	240 ms	108064 KB	Output is correct
14	Correct	257 ms	109072 KB	Output is correct
15	Correct	434 ms	199576 KB	Output is correct
16	Correct	431 ms	201384 KB	Output is correct
17	Correct	250 ms	112720 KB	Output is correct
18	Correct	257 ms	113032 KB	Output is correct
19	Correct	423 ms	205584 KB	Output is correct
20	Correct	438 ms	205684 KB	Output is correct