#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll NMAX = 250002;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;
vector <int> events[NMAX];
vector <int> queries[NMAX];
int t[NMAX];
pii q[NMAX];
int qq;
struct Node{
int total, maxSuff;
}aint[NMAX * 4];
Node combine(Node a, Node b){
Node sol = {a.total + b.total, max({b.maxSuff, a.maxSuff + b.total})};
/// Am nevoie de cel mai mare sufix care se TERMINA IN MINE
return sol;
}
void update(int node, int st, int dr, int a, int b){
if(st == dr){
aint[node] = {b, max(0, b)};
return;
}
int mid = (st + dr) / 2;
if(a <= mid)
update(node * 2, st, mid, a, b);
else update(node * 2 + 1, mid + 1, dr, a, b);
aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}
Node maxSuff(int node, int st, int dr, int a, int b){
if(a <= st && dr <= b){
return aint[node];
}
int mid = (st + dr) / 2;
Node sol = {0, 0};
if(a <= mid) sol = combine(sol, maxSuff(node * 2, st, mid, a, b));
if(b > mid) sol = combine(sol, maxSuff(node * 2 + 1, mid + 1, dr, a, b));
return sol;
}
pii aib[NMAX];
void baga(pii x, int val){
aib[x.first].second = x.second;
for(; x.first <= qq; x.first += x.first&(-x.first))
aib[x.first].first += val;
}
int query(int x){
int sol = 0;
for(; x; x -= x&(-x))
sol += aib[x].first;
return sol;
}
int Search(int x){
int r = 0, pas = (1 << nrbits), s = 0;
while(pas){
if(r + pas <= qq && (s + aib[r + pas].first) < x)
r += pas;
pas /= 2;
}
r++;
return aib[r].second;
}
signed main() {
#ifdef HOME
ifstream cin(".in");
ofstream cout(".out");
#endif // HOME
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, i;
for(i = 0; i < NMAX * 4; i++) aint[i] = {0, 0};
cin >> n >> m >> qq;
for(i = 1; i <= qq; i++){
cin >> t[i];
if(t[i] == 3){
cin >> q[i].first >> q[i].second;
queries[q[i].first].push_back(i);
}else if(t[i] == 2){
int l, r;
cin >> l >> r >> q[i].first;
events[l].push_back(i);
events[r + 1].push_back(-i);
}else{
int l, r;
cin >> l >> r >> q[i].second >> q[i].first;
events[l].push_back(i);
events[r + 1].push_back(-i);
}
}
for(i = 1; i <= n; i++){
for(auto x : events[i]){
if(x < 0){
baga({-x, q[-x].second}, -q[-x].first);
update(1, 1, qq, -x, 0);
}else{
if(t[x] == 1){
baga({x, q[x].second}, q[x].first);
update(1, 1, qq, x, q[x].first);
}else{
update(1, 1, qq, x, -q[x].first);
}
}
}
for(auto x : queries[i]){
int untilNow = query(x);
int currentSize = maxSuff(1, 1, qq, 1, x).maxSuff;
int b = q[x].second;
if(b <= currentSize)
cout << Search(untilNow - currentSize + b) << "\n";
else
cout << "0\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
24408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
24408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
32108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
243 ms |
41624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
24408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
30904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
24408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
24408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
