#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(v) v.begin(), v.end()
const int INF = 0x3f3f3f3f;
int N;
struct Seg {
struct Node {int s, e, l, r, v, la, lb, sa, sb;};
vector<Node> t;
void init(int s, int e, int v) {t.push_back({s, e, -1, -1, v, INF, 0, INF, 0});}
void prop(int n, int s, int e) {
if (t[n].la != INF) {
if (t[n].la < 0) t[n].v = t[n].la*s+t[n].lb;
else t[n].v = t[n].la*e+t[n].lb;
}
else t[n].v += t[n].lb;
if (s == e) {
t[n].la = INF;
t[n].lb = 0;
return;
}
if (t[n].la != INF) {
t[n].sa = t[n].la;
t[n].sb = t[n].lb;
}
else t[n].sb += t[n].lb;
if (t[n].l != -1) {
if (t[n].la != INF) {
t[t[n].l].la = t[n].la;
t[t[n].l].lb = t[n].lb;
}
else t[t[n].l].lb += t[n].lb;
}
if (t[n].r != -1) {
if (t[n].la != INF) {
t[t[n].r].la = t[n].la;
t[t[n].r].lb = t[n].lb;
}
else t[t[n].r].lb += t[n].lb;
}
t[n].la = INF;
t[n].lb = 0;
}
void update(int n, int s, int e, int l, int r, int a, int b) {
prop(n, s, e);
if (l <= s && e <= r) {
if (a == INF) t[n].lb += b;
else {
t[n].la = a;
t[n].lb = b;
}
prop(n, s, e);
return;
}
if (e < l || s > r) return;
int m = (s+e)/2;
if (t[n].l == -1) {
t[n].l = t.size();
init(s, m, 0);
t[t[n].l].la = t[n].sa;
t[t[n].l].lb = t[n].sb;
}
if (t[n].r == -1) {
t[n].r = t.size();
init(m+1, e, 0);
t[t[n].r].la = t[n].sa;
t[t[n].r].lb = t[n].sb;
}
update(t[n].l, s, m, l, r, a, b);
update(t[n].r, m+1, e, l, r, a, b);
t[n].v = max(t[t[n].l].v, t[t[n].r].v);
}
int get(int n, int s, int e, int idx) {
prop(n, s, e);
if (s == e) return t[n].v;
int m = (s+e)/2;
if (idx <= m) {
if (t[n].l == -1) {
if (e-s == 1) {
if (t[n].sa == INF) return t[n].sb;
else return t[n].sa*s+t[n].sb;
}
t[n].l = t.size();
init(s, m, 0);
t[t[n].l].la = t[n].sa;
t[t[n].l].lb = t[n].sb;
}
return get(t[n].l, s, m, idx);
}
else {
if (t[n].r == -1) {
if (e-s == 1) {
if (t[n].sa == INF) return t[n].sb;
else return t[n].sa*e+t[n].sb;
}
t[n].r = t.size();
init(m+1, e, 0);
t[t[n].r].la = t[n].sa;
t[t[n].r].lb = t[n].sb;
}
return get(t[n].r, m+1, e, idx);
}
}
int query(int n, int s, int e, int x) {
prop(n, s, e);
if (s == e) {
if (t[n].v > x) return s-1;
else return s;
}
int m = (s+e)/2;
int left;
if (t[n].l != -1) {
if (t[t[n].l].la == INF) left = t[t[n].l].v + t[t[n].l].lb;
else {
if (t[t[n].l].la < 0) left = t[t[n].l].la*s + t[t[n].l].lb;
else left = t[t[n].l].la*m + t[t[n].l].lb;
}
}
else {
if (t[n].sa == INF) left = t[n].sb;
else {
if (t[n].sa < 0) left = t[n].sa*s + t[n].sb;
else left = t[n].sa*m + t[n].sb;
}
}
if (left > x) {
if (t[n].l == -1) {
if (e-s == 1) {
int cur;
if (t[n].sa == INF) cur = t[n].sb;
else cur = t[n].sa*s+t[n].sb;
if (cur > x) return s-1;
else return s;
}
t[n].l = t.size();
init(s, m, 0);
t[t[n].l].la = t[n].sa;
t[t[n].l].lb = t[n].sb;
}
return query(t[n].l, s, m, x);
}
else {
if (t[n].r == -1) {
if (e-s == 1) {
int cur;
if (t[n].sa == INF) cur = t[n].sb;
else cur = t[n].sa*e+t[n].sb;
if (cur > x) return e-1;
else return e;
}
t[n].r = t.size();
init(m+1, e, 0);
t[t[n].r].la = t[n].sa;
t[t[n].r].lb = t[n].sb;
}
return query(t[n].r, m+1, e, x);
}
}
}seg;
vector<int> arr, comp;
void solve() {
cin >> N;
seg.init(0, N, 0);
while (true) {
char op; cin >> op;
if (op == 'I') {
int l, r, d; cin >> l >> r >> d;
int pv = seg.get(0, 0, N, l-1)-(l-1)*d;
int pv2 = pv+r*d-seg.get(0, 0, N, r);
seg.update(0, 0, N, l, r, d, pv);
if (r != N) seg.update(0, 0, N, r+1, N, INF, pv2);
}
if (op == 'Q') {
int x; cin >> x;
cout << seg.query(0, 0, N, x) << '\n';
//for (int i = 0; i <= N; i++) cout << seg.get(0, 0, N, i) << ' '; cout << '\n';
}
if (op == 'E') break;
}
}
int main(void) {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1; //cin >> T;
while (T--) solve();
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc2dn1Tc.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4E6hmb.o:mountains.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc2dn1Tc.o: in function `main':
grader.cpp:(.text.startup+0x238): undefined reference to `maximum_deevs(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
