| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1246036 | inkvizytor | 게임 (IOI14_game) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct vert {
int s = 0, l = -1, p = -1;
bool f = 0;
};
void push(int v, vector<vert> &tr) {
if (tr[v].l != -1) {
if (tr[v].f) {
tr[tr[v].l].s = tr[v].s/2;
tr[tr[v].p].s = tr[v].s/2;
tr[tr[v].l].f = 1;
tr[tr[v].p].f = 1;
}
return;
}
tr[v].l = tr.size();
tr.push_back(vert());
tr[v].p = tr.size();
tr.push_back(vert());
if (tr[v].f) {
tr[tr[v].l].s = tr[v].s/2;
tr[tr[v].p].s = tr[v].s/2;
tr[tr[v].l].f = 1;
tr[tr[v].p].f = 1;
}
}
void add (int v, int p, int k, vector<vert> &tr, int a, int b) {
if (a <= p && k <= b) {
tr[v].s = k-p+1;
tr[v].f = 1;
return;
}
if (b < p || a > k) {
return;
}
push(v, tr);
add(tr[v].l, p, (p+k)/2, tr, a, b);
add(tr[v].p, (p+k)/2+1, k, tr, a, b);
tr[v].s= tr[tr[v].l].s+tr[tr[v].p].s;
}
int sum(int v, int p, int k, vector<vert> &tr, int a, int b) {
if (a <= p && k <= b) {
return tr[v].s;
}
if (b < p || a > k) {
return 0;
}
push(v, tr);
return sum(tr[v].l, p, (p+k)/2, tr, a, b)+sum(tr[v].p, (p+k)/2+1, k, tr, a, b);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<vert> tr (2);
int c = 0;
for (int i = 0; i < n; i++) {
int d, x, y;
cin >> d >> x >> y;
x+=c, y+=c;
if (d==1) {
int a = sum(1, 0, (1<<30)-1, tr, x, y);
c = a;
cout << a << '\n';
}
else {
add(1, 0, (1<<30)-1, tr, x, y);
}
}
}