Submission #783252

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
783252	2023-07-14T18:55:55 Z	AmirElarbi	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	344 ms	139412 KB

apple

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define INF 1e9+5
#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(!c[0]) c[0] = new node();
        c[0]->update(l,md,i,j);
        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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	14 ms	3436 KB	Output is correct
5	Correct	17 ms	4180 KB	Output is correct
6	Correct	16 ms	3972 KB	Output is correct
7	Correct	17 ms	4160 KB	Output is correct
8	Correct	109 ms	30044 KB	Output is correct
9	Correct	230 ms	52280 KB	Output is correct
10	Correct	254 ms	57664 KB	Output is correct
11	Correct	240 ms	61884 KB	Output is correct
12	Correct	265 ms	63736 KB	Output is correct
13	Correct	234 ms	74296 KB	Output is correct
14	Correct	279 ms	74932 KB	Output is correct
15	Correct	337 ms	135452 KB	Output is correct
16	Correct	341 ms	136472 KB	Output is correct
17	Correct	234 ms	77420 KB	Output is correct
18	Correct	233 ms	77440 KB	Output is correct
19	Correct	344 ms	139400 KB	Output is correct
20	Correct	335 ms	139412 KB	Output is correct