Submission #898626

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
898626	2024-01-04T23:39:56 Z	trMatherz	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	435 ms	207760 KB

apple

#include <bits/stdc++.h>
using namespace std;
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	0 ms	344 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	13 ms	5980 KB	Output is correct
6	Correct	13 ms	5976 KB	Output is correct
7	Correct	13 ms	5980 KB	Output is correct
8	Correct	114 ms	44624 KB	Output is correct
9	Correct	256 ms	77332 KB	Output is correct
10	Correct	258 ms	85368 KB	Output is correct
11	Correct	261 ms	91732 KB	Output is correct
12	Correct	263 ms	94544 KB	Output is correct
13	Correct	263 ms	110084 KB	Output is correct
14	Correct	256 ms	111216 KB	Output is correct
15	Correct	428 ms	201808 KB	Output is correct
16	Correct	430 ms	203556 KB	Output is correct
17	Correct	254 ms	114676 KB	Output is correct
18	Correct	272 ms	114948 KB	Output is correct
19	Correct	431 ms	207644 KB	Output is correct
20	Correct	435 ms	207760 KB	Output is correct