Submission #16884

#	Time	Username	Problem	Language	Result	Execution time	Memory
16884		murat	Monkey and Apple-trees (IZhO12_apple)	C++98	100 / 100	71 ms	1720 KiB

apple

#include <bits/stdc++.h>

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 2e5 + 5;

int t, m, x, y, c;

class node{
    public:
        int cnt, L;
        node *l, *r;
        node() { L = cnt = 0; l = r = NULL; }
};
typedef node* pnode;
pnode ST = new node;

int query(pnode &ST, int bas, int son, int x, int y) {
    if(!ST || bas > y || son < x) return 0;
    if(ST->L == 1) { return min(son,y) - max(x, bas) + 1; }
    if(x <= bas && son <= y) return ST->cnt;
    return query(ST->l, bas, orta, x, y) + query(ST->r, orta+1, son, x, y);
}

int update(pnode &ST, int bas, int son, int x, int y) {
    if(ST->L) return ST->cnt;
    if(bas > y || son < x) return ST->cnt;
    if(x <= bas && son <= y) { ST->L = 1; return ST->cnt = (son - bas + 1); }
    if(ST->l == NULL) ST->l = new node;
    if(ST->r == NULL) ST->r = new node;
    return ST->cnt = update(ST->l, bas, orta, x, y) + update(ST->r, orta+1, son, x, y);
}

int main() {
    ST = new node;
    scanf("%d", &m);
    FOR(i, 1, m) {
        scanf("%d %d %d", &t, &x, &y);
        if(t == 2) update(ST, 1, inf, x+c, y+c);
        else printf("%d\n",c = query(ST, 1, inf, x+c, y+c));
    }
    return 0;
}

• Subtask 1: 100 / 100