/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 100007
#define MAXE 100007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
/// code from USACO examples
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;
int Q;
/// ------ Segment Treee --------
int Nseg[2];
int vct;
struct SEGNODE {
int lpt, rpt;
int sum; /// sum is always updated before lazy value is used.
bool LazyPushedDown; /// flag whether we already pushed down the lazy additional value
};
SEGNODE seg[600007]; /// max 2e5 unique y, which needs 2^19 for Nseg
void newSegNode(int v) {
seg[v].lpt = -1; seg[v].rpt = -1;
seg[v].sum = 0;
seg[v].LazyPushedDown = true;
}
void initSeg() {
/// build a segment tree for array of interest indexed from Nseg[0] to Nseg[1]
Nseg[0] = 1;
Nseg[1] = 1e9;
vct = 1;
newSegNode(vct);
}
void pullUp(int v, int l, int m, int r) {
if(l==r) return;
int ans1 = (seg[v].lpt == -1) ? 0 : seg[seg[v].lpt].sum;
int ans2 = (seg[v].rpt == -1) ? 0 : seg[seg[v].rpt].sum;
seg[v].sum = ans1 + ans2;
}
void pushDown(int v, int l, int m, int r) {
if(l==r) {
seg[v].LazyPushedDown = true;
return;
}
if(seg[v].LazyPushedDown) return;
/// push down
int v1 = seg[v].lpt, v2 = seg[v].rpt;
if(v1 == -1) {
vct++; newSegNode(vct);
seg[v].lpt = vct;
v1 = vct;
}
seg[v1].sum = (m - l + 1);
seg[v1].LazyPushedDown = false;
if(v2 == -1) {
vct++; newSegNode(vct);
seg[v].rpt = vct;
v2 = vct;
}
seg[v2].sum = (r - (m+1) + 1);
seg[v2].LazyPushedDown = false;
/// update v
seg[v].LazyPushedDown = true;
}
ll querySeg(int qle, int qri, int v = 1, int l = Nseg[0], int r = Nseg[1]) {
if(r < qle || l > qri) return 0;
if(qle <= l && r <= qri) {
return seg[v].sum;
}
int mid = (l + r) / 2;
pushDown(v, l, mid, r);
int ans1 = 0, ans2 = 0;
if(qle <= mid) {
if(seg[v].lpt == -1) {
ans1 = 0;
} else {
ans1 = querySeg(qle, qri, seg[v].lpt, l, mid);
}
}
if(qri >= mid+1) {
if(seg[v].rpt == -1) {
ans2 = 0;
} else {
ans2 = querySeg(qle, qri, seg[v].rpt, mid+1, r);
}
}
pullUp(v, l, mid, r);
return ans1 + ans2;
}
void updateSeg(int ule, int uri, int v = 1, int l = Nseg[0], int r = Nseg[1]){
if(r < ule || l > uri) return;
int mid = (l + r) / 2;
if(ule <= l && r <= uri) {
pushDown(v, l, mid, r);
seg[v].sum = (r - l + 1);
seg[v].LazyPushedDown = false;
return;
}
pushDown(v, l, mid, r);
if(ule <= mid) {
if(seg[v].lpt == -1) {
vct++; newSegNode(vct);
seg[v].lpt = vct;
}
if(debug) cout << " .. go left {" << l << "," << mid << "}" << endl;
updateSeg(ule, uri, seg[v].lpt, l, mid);
}
if(uri >= mid+1) {
if(seg[v].rpt == -1) {
vct++; newSegNode(vct);
seg[v].rpt = vct;
}
if(debug) cout << " .. go right {" << mid+1 << "," << r << "}" << endl;
updateSeg(ule, uri, seg[v].rpt, mid+1, r);
}
pullUp(v, l, mid, r);
}
int main() {
debug = false; submit = false;
if(submit) setIO("testName");
int i, j, k;
int c = 0;
cin >> Q ;
initSeg();
for(i=0; i<Q; i++) {
int cmd, a, b;
cin >> cmd >> a >> b;
if(cmd == 2) {
updateSeg(a+c, b+c);
} else {
c = querySeg(a+c, b+c);
cout << c << endl;
}
}
}
Compilation message
apple.cpp: In function 'int main()':
apple.cpp:191:12: warning: unused variable 'j' [-Wunused-variable]
191 | int i, j, k;
| ^
apple.cpp:191:15: warning: unused variable 'k' [-Wunused-variable]
191 | int i, j, k;
| ^
apple.cpp: In function 'void setIO(std::string)':
apple.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
52 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
53 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
29 ms |
2284 KB |
Output is correct |
| 5 |
Correct |
33 ms |
2796 KB |
Output is correct |
| 6 |
Correct |
34 ms |
2680 KB |
Output is correct |
| 7 |
Correct |
33 ms |
2796 KB |
Output is correct |
| 8 |
Incorrect |
190 ms |
10624 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
