Submission #783253

#	Time	Username	Problem	Language	Result	Execution time	Memory
783253		AmirElarbi	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	331 ms	137216 KiB

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 / 100