#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "IZhO12_apple"
void Fi(){
if(fopen(PROB".inp", "r")){
freopen(PROB".inp", "r", stdin);
freopen(PROB".out", "w", stdout);
}
}
const int M = 1e5 + 1;
struct node{
int sum, lz, be, en, l, r;
node(): sum(0), lz(0), l(-1), r(-1) {}
};
node ST[M * 64];
int cnt = 1;
void down(const int &id){
int mi = (ST[id].be + ST[id].en) / 2;
if(ST[id].l == -1){
ST[id].l = ++cnt;
ST[cnt].be = ST[id].be;
ST[cnt].en = mi;
}
if(ST[id].r == -1){
ST[id].r = ++cnt;
ST[cnt].be = mi + 1;
ST[cnt].en = ST[id].en;
}
if(ST[id].lz){
ST[ST[id].l].lz = ST[ST[id].r].lz = ST[id].lz;
ST[ST[id].l].sum = (mi - ST[id].be + 1);
ST[ST[id].r].sum = (ST[id].en - mi);
ST[id].lz = 0;
}
}
void update(const int &l, const int &r, const int &v, int id = 1){
if(l <= ST[id].be && ST[id].en <= r){
ST[id].sum = (ST[id].en - ST[id].be + 1);
ST[id].lz = 1;
return;
}
int mi = (ST[id].be + ST[id].en) / 2;
if(ST[id].l == -1){
ST[id].l = ++cnt;
ST[cnt].be = ST[id].be;
ST[cnt].en = mi;
}
if(ST[id].r == -1){
ST[id].r = ++cnt;
ST[cnt].be = mi + 1;
ST[cnt].en = ST[id].en;
}
down(id);
if(l <= mi) update(l, r, v, ST[id].l);
if(mi < r) update(l, r, v, ST[id]. r);
ST[id].sum = ST[ST[id].l].sum + ST[ST[id].r].sum;
}
int query(const int &l, const int &r, int id = 1){
if(l <= ST[id].be && ST[id].en <= r) return ST[id].sum;
int mi = (ST[id].be + ST[id].en) / 2;
down(id);
int ret = 0;
if(l <= mi) ret += query(l, r, ST[id].l);
if(mi < r) ret += query(l, r, ST[id].r);
return ret;
}
int C;
int main(){
IOS;
Fi();
int m; cin >> m;
ST[1].be = 1, ST[1].en = 1e9;
while(m--){
int t, x, y; cin >> t >> x >> y;
if(t == 2) update(x + C, y + C, 1);
else cout << (C = query(x + C, y + C)) << "\n";
}
return 0;
}
Compilation message
apple.cpp: In function 'void Fi()':
apple.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen(PROB".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | freopen(PROB".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
150552 KB |
Output is correct |
| 2 |
Correct |
59 ms |
150596 KB |
Output is correct |
| 3 |
Correct |
59 ms |
150596 KB |
Output is correct |
| 4 |
Correct |
72 ms |
150708 KB |
Output is correct |
| 5 |
Correct |
84 ms |
150764 KB |
Output is correct |
| 6 |
Correct |
75 ms |
150708 KB |
Output is correct |
| 7 |
Correct |
81 ms |
150784 KB |
Output is correct |
| 8 |
Correct |
190 ms |
151624 KB |
Output is correct |
| 9 |
Correct |
304 ms |
152716 KB |
Output is correct |
| 10 |
Correct |
309 ms |
152644 KB |
Output is correct |
| 11 |
Correct |
321 ms |
152712 KB |
Output is correct |
| 12 |
Correct |
318 ms |
152708 KB |
Output is correct |
| 13 |
Correct |
302 ms |
153264 KB |
Output is correct |
| 14 |
Correct |
295 ms |
153064 KB |
Output is correct |
| 15 |
Correct |
402 ms |
153148 KB |
Output is correct |
| 16 |
Correct |
387 ms |
153356 KB |
Output is correct |
| 17 |
Correct |
313 ms |
153308 KB |
Output is correct |
| 18 |
Correct |
294 ms |
153144 KB |
Output is correct |
| 19 |
Correct |
399 ms |
153404 KB |
Output is correct |
| 20 |
Correct |
391 ms |
153248 KB |
Output is correct |
