Submission #783253

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
783253	2023-07-14T18:56:27 Z	AmirElarbi	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	331 ms	137216 KB

apple

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define INF 1e9
#define ve vector
#define vi ve<int>
#define ii pair<int,int>
#define vii ve<ii>
#define pb push_back
#define fi first
#define se second
using namespace __gnu_pbds;
using namespace std;
const int MOD = 1e9+7;
const int nax = 1e5+5;
const int kax = 25+5;
#include<bits/stdc++.h>
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> struct node
{
    T val = 0; T lazy = 0;  node<T>* c[2];
    node() {c[0] = c[1] = NULL; }
    void push_lazy(int l, int r){
        if(lazy){
            int md = (l+r)/2;
            if(!c[0]) c[0] = new node(); 
            c[0]->val = (md-l+1);
            if(!c[1]) c[1] = new node();
            c[1]->val = (r-md);
            c[0]->lazy = c[1]->lazy = 1;
            lazy = 0; 
        }
    }
    void update(int l, int r, int i, int j){
        if(r < i || l > j) return;
        if(i <= l && r <= j){ val = (r-l+1); lazy = 1; return; }
        push_lazy(l,r);
        int md = (l+r)/2;
        if(i <= md){
            if(!c[0]) c[0] = new node();
            c[0]->update(l,md,i,j);
        } 
        if(j > md){
            if(!c[1]) c[1] = new node();
            c[1]->update(md+1,r,i,j);
        }
        val = 0;
        for(int i = 0; i < 2; i++) if(c[i]) val += c[i]->val;
        //cout << l << ' ' << r << " " << val << endl;
    }
    T query(int l, int r, int i, int j) {
        if(r < i || l > j) return 0;
        if(i <= l && r <= j) return val;
        push_lazy(l,r);
        int md = (l+r)/2; T res = 0;
        if(c[0]) res += c[0]->query(l,md,i,j);
        if(c[1]) res += c[1]->query(md+1,r,i,j);
        return res;
    }
};
 
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int m;
    cin >> m;
    int c = 0;
    node<int> rt = node<int>();
    for (int i = 0; i < m; ++i)
    {
        int d, x, y;
        cin >> d >> x >> y;
        x--,y--;
        if(d == 1){
            int ans = rt.query(0,INF, x+c, y+c);
            cout << ans << endl;
            c = ans;
        } else {
            //cout << x+c << " " << y+c << endl;
            rt.update(0,INF,x+c, y+c);
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	13 ms	3300 KB	Output is correct
5	Correct	16 ms	4052 KB	Output is correct
6	Correct	16 ms	3840 KB	Output is correct
7	Correct	16 ms	3924 KB	Output is correct
8	Correct	112 ms	29244 KB	Output is correct
9	Correct	215 ms	50512 KB	Output is correct
10	Correct	234 ms	56044 KB	Output is correct
11	Correct	249 ms	60108 KB	Output is correct
12	Correct	236 ms	62024 KB	Output is correct
13	Correct	225 ms	72260 KB	Output is correct
14	Correct	221 ms	72848 KB	Output is correct
15	Correct	319 ms	133196 KB	Output is correct
16	Correct	331 ms	134324 KB	Output is correct
17	Correct	222 ms	75340 KB	Output is correct
18	Correct	219 ms	75428 KB	Output is correct
19	Correct	329 ms	137140 KB	Output is correct
20	Correct	319 ms	137216 KB	Output is correct