#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const ll inf = numeric_limits<ll> :: max();
struct STB{
vector<ll> a;
int n;
STB(int ns){
n = ns;
a.resize(n + 1);
}
void add(int l, int r, ll x){
for (int i = l; i <= r; i++){
a[i] += x;
}
}
void chmax(int l, int r, ll x){
for (int i = l; i <= r; i++){
a[i] = max(a[i], x);
}
}
ll get(int p){
return a[p];
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, q; cin>>n>>m>>q;
STB C(n);
const int S = sqrt(n);
const int sz = ceil(1.0 * n / S) - 1;
vector<int> st[n + 1], st1[sz + 5];
vector<ll> pr[n + 1], pr1[sz + 5];
vector<int> bc(n + 1);
int i = 1, j = S, k = 0;
while (i <= n){
while (i <= j) bc[i++] = k;
j = min(n, j + S);
k++;
}
vector<int> col(q + 1);
for (int tt = 1; tt <= q; tt++){
int type; cin>>type;
if (type == 1){
int l, r, c, k; cin>>l>>r>>c>>k;
col[tt] = c;
C.add(l, r, k);
int bl = bc[l] + 1, br = bc[r] - 1;
for (int i = bl; i <= br; i++){
st1[i].pb(tt);
if (pr1[i].empty()) pr1[i].pb(k);
else pr1[i].pb(pr1[i].back() + k);
}
for (int i = l; i <= S * bl; i++){
st[i].pb(tt);
if (pr[i].empty()) pr[i].pb(k);
else pr[i].pb(pr[i].back() + k);
}
for (int i = S * (br + 1) + 1; i <= r; i++){
st[i].pb(tt);
if (pr[i].empty()) pr[i].pb(k);
else pr[i].pb(pr[i].back() + k);
}
}
else if (type == 2){
int l, r, k; cin>>l>>r>>k;
C.add(l, r, -k);
C.chmax(1, n, 0);
}
else {
int a; ll b; cin>>a>>b;
ll v = C.get(a);
if (b > v){
cout<<0<<"\n";
continue;
}
b -= v;
if (!pr1[bc[a]].empty()) b += pr1[bc[a]].back();
if (!pr[a].empty()) b += pr[a].back();
auto low = [&](vector<int>& x, int t){
if (x.empty() || x[0] > t) return -1;
int l = 0, r = (int) x.size() - 1;
while (l + 1 < r){
int m = (l + r) / 2;
if (x[m] <= t){
l = m;
}
else {
r = m - 1;
}
}
if (x[r] <= t) l = r;
return l;
};
auto check = [&](int m){
int j1 = low(st1[bc[a]], m);
int j2 = low(st[a], m);
ll val = 0;
if (j1 >= 0) val += pr1[bc[a]][j1];
if (j2 >= 0) val += pr[a][j2];
return (val >= b);
};
int l = 1, r = tt;
while (l + 1 < r){
int m = (l + r) / 2;
if (check(m)){
r = m;
}
else {
l = m + 1;
}
}
if (check(l)) r = l;
cout<<col[r]<<"\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
13912 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1069 ms |
89400 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
68 ms |
42244 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
