#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef queue<int> qi;
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
#define FOR(i,a,b) for (int i=a; i<=b; i++)
#define FOR_(i,a,b,x) for (int i=a; i<=b; i+=x)
#define FOR_x(x,v) for (auto x : v)
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+1;
const ll MOD = 10e7;
//? link: https://oj.uz/problem/view/IZhO12_apple
//? sol: dynamic/sparse segtree + lazy propagation
//! INCORRECT
//? FIXED
// -> probably something wrong with update, cause repeated queries fixes the problem
// -> mostly edited from template, later altered a bit according to official SOL
const int SZ = 1e9; // max size of tree
template<class T> struct node { // T = type parameter -> any type
T val=0, lazy=0;
T lr, rr; // lr=left range, rr=right range
node<T>* lc; // lc = left child; * = pointer
node<T>* rc; // rc = right child
node(T lrr, T rrr) { // constructor
lc = rc = NULL;
lr = lrr, rr = rrr;
}
// inline T get_val() { return (lazy ? rr-lr+1 : val); }
inline T get_val() { return val; }
void push_lazy() {
if (lazy) {
val = rr-lr+1;
lazy = 0;
if (val==1) return;
int mid = (lr+rr)>>1;
if (!lc) lc=new node(lr,mid);
if (!rc) rc=new node(mid+1,rr);
lc->lazy = rc->lazy = 1;
}
}
void update(int l, int r) { // update node value
push_lazy();
int s = lr, t = rr;
if (l<=s && t<=r) {
lazy = 1;
push_lazy();
return;
}
int mid = (s+t)>>1;
if (l<=mid) {
if (!lc) lc=new node(s,mid);
lc -> update(l, r);
}
if (r>mid) {
if (!rc) rc=new node(mid+1,t);
rc -> update(l, r);
}
if (lc) lc -> push_lazy();
if (rc) rc -> push_lazy();
val = (lc ? lc->get_val() : 0) + (rc ? rc->get_val() : 0);
// printf("%d:%d -> %d\n",s,t,val);
// push_lazy();
}
T query(int l, int r) {
int s = lr, t = rr;
push_lazy();
// cout << lr << " " << rr << " " << val << " " << lazy << endl;
if (l<=s && t<=r) return val;
int mid = (s+t)>>1;
T cnt = 0;
if (l<=mid) {
if (!lc) lc = new node(s,mid);
cnt += lc->query(l,r);
}
if (r>mid) {
if (!rc) rc = new node(mid+1,t);
cnt += rc->query(l,r);
}
return cnt;
}
void debugQ(int level) {
// cout << level << " " << lr << " " << rr << " " << val << " " << lazy << endl;
if (lc) lc->debugQ(level+1);
if (rc) rc->debugQ(level+1);
}
};
int m, c=0;
node<int> root(1,SZ); // root node
int main()
{
// faster cin/cout
ios_base::sync_with_stdio(false);
cin.tie(NULL);
freopen("F.in","r",stdin);
freopen("F.out","w",stdout);
cin >> m;
while (m--) {
int d,x,y; cin>>d>>x>>y;
if (d==1) {
root.debugQ(0);
c = root.query(x+c,y+c);
cout << c << endl;
}
else {
root.update(x+c,y+c);
// FOR(i,1,10) cout << root.query(i,i) << " ";
// cout << endl;
}
}
return 0;
}
Compilation message
apple.cpp: In function 'int main()':
apple.cpp:110:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | freopen("F.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~
apple.cpp:111:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | freopen("F.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
