#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x) (std::isinf(x))
#define IS_NAN(x) (std::isnan(x))
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div ___div
#define prev ___prev
#define next ___next
#define left ___leftc
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define __Im_sobad__ main()
#define __builtin_popcount __builtin_popcountll
using namespace std;
/*
Phung Duc Minh will win hsgtp 2025
Phung Duc Minh will become top 1 ams
Phung Duc Minh will be winner of IOI 2028
I love you so much but you can see(8E) !!!! ...
Make 8E GRATE AGAIN!!!
*/
const int MAXN = 1e5 + 5;
int n;
class SparseSegmentTree {
public:
struct Node {
int sum, pre, lazy;
bool isLazy;
Node *left, *right;
Node() {
sum = pre = lazy = 0;
isLazy = false; left = right = nullptr;
}
};
Node* root = new Node;
void push(Node* idx, int l, int r) {
if(!idx->left) idx->left = new Node;
if(!idx->right) idx->right = new Node;
if(idx->isLazy) {
int mid = (l + r) >> 1;
idx->left->sum = idx->lazy * (mid - l + 1);
idx->right->sum = idx->lazy * (r - mid);
idx->left->pre = max(0, idx->lazy * (mid - l + 1));
idx->right->pre = max(0, idx->lazy * (r - mid));
idx->left->lazy = idx->right->lazy = idx->lazy;
idx->left->isLazy = idx->right->isLazy = true;
idx->lazy = 0; idx->isLazy = false;
}
}
void update(Node* idx, int l, int r, int u, int v, int val) {
if(r < u || v < l) return;
if(u <= l && r <= v) {
idx->sum = val * (r - l + 1);
idx->pre = max(0, val * (r - l + 1)); idx->lazy = val;
idx->isLazy = true;
return;
}
int mid = (l + r) >> 1;
push(idx, l, r);
update(idx->left, l, mid, u, v, val);
update(idx->right, mid + 1, r, u, v, val);
idx->sum = idx->left->sum + idx->right->sum;
idx->pre = max(idx->left->pre, idx->left->sum + idx->right->pre);
}
int FindK(Node* idx, int l, int r, pair<int, int> prefix, int tmp) {
if(l == r) return l;
int mid = (l + r) >> 1;
push(idx, l, r);
pair<int, int> val;
// trick
val.first = prefix.first + idx->left->sum;
val.second = max(prefix.second, prefix.first + idx->left->pre);
if(tmp < val.second) return FindK(idx->left, l, mid, prefix, tmp);
return FindK(idx->right, mid + 1, r, val, tmp);
}
};
void solve() {
cin >> n; SparseSegmentTree myit;
while(true) {
char type; int a, b, d;
cin >> type;
if(type == 'E') break;
if(type == 'I') cin >> a >> b >> d;
else if(type == 'Q') cin >> a;
if(type == 'I') myit.update(myit.root, 1, n, a, b, d);
else {
if(a >= myit.root->pre) cout << n << "\n";
else cout << myit.FindK(myit.root, 1, n, {0, 0}, a) - 1 << "\n";
}
}
}
__Im_sobad__{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
cerr << "Time elapsed: " << TIME << " s.\n";
return 0;
}
// Author: Phung Duc Minh
// Look at my code, my code is so amazing and legit
// Try to be better!
Compilation message (stderr)
apple.cpp:19:22: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
19 | #define __Im_sobad__ main()
| ^~~~
apple.cpp:99:1: note: in expansion of macro '__Im_sobad__'
99 | __Im_sobad__{
| ^~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
