Submission #771449

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
771449	2023-07-03T03:14:32 Z	taitruong270	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	445 ms	207732 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	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	11 ms	4820 KB	Output is correct
5	Correct	13 ms	5844 KB	Output is correct
6	Correct	13 ms	5652 KB	Output is correct
7	Correct	13 ms	5844 KB	Output is correct
8	Correct	117 ms	43656 KB	Output is correct
9	Correct	249 ms	75556 KB	Output is correct
10	Correct	249 ms	83608 KB	Output is correct
11	Correct	304 ms	89804 KB	Output is correct
12	Correct	276 ms	92748 KB	Output is correct
13	Correct	248 ms	110000 KB	Output is correct
14	Correct	250 ms	111068 KB	Output is correct
15	Correct	445 ms	201752 KB	Output is correct
16	Correct	429 ms	203428 KB	Output is correct
17	Correct	249 ms	114780 KB	Output is correct
18	Correct	269 ms	114896 KB	Output is correct
19	Correct	436 ms	207732 KB	Output is correct
20	Correct	432 ms	207704 KB	Output is correct