답안 #16884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16884	2015-10-24T11:54:31 Z	murat	원숭이와 사과 나무 (IZhO12_apple)	C++	100 / 100	71 ms	1720 KB

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1720 KB	Output is correct
2	Correct	0 ms	1720 KB	Output is correct
3	Correct	0 ms	1720 KB	Output is correct
4	Correct	0 ms	1720 KB	Output is correct
5	Correct	0 ms	1720 KB	Output is correct
6	Correct	0 ms	1720 KB	Output is correct
7	Correct	7 ms	1720 KB	Output is correct
8	Correct	27 ms	1720 KB	Output is correct
9	Correct	0 ms	1720 KB	Output is correct
10	Correct	0 ms	1720 KB	Output is correct
11	Correct	53 ms	1720 KB	Output is correct
12	Correct	54 ms	1720 KB	Output is correct
13	Correct	0 ms	1720 KB	Output is correct
14	Correct	0 ms	1720 KB	Output is correct
15	Correct	42 ms	1720 KB	Output is correct
16	Correct	47 ms	1720 KB	Output is correct
17	Correct	48 ms	1720 KB	Output is correct
18	Correct	46 ms	1720 KB	Output is correct
19	Correct	56 ms	1720 KB	Output is correct
20	Correct	71 ms	1720 KB	Output is correct