#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)
#define int ll
using namespace std;
template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2>
void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}
template<class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}
template<class T>
void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
struct fen{
vector<ll> val;
int n;
fen(int _n = 0){
n = _n;
val.resize(n + 3, 0);
}
void upd(int p, ll c){
while(p <= n){
val[p] += c;
p += p & -p;
}
}
ll get(int p){
ll ans = 0;
while(p > 0){
ans += val[p];
p -= p & -p;
}
return ans;
}
};
struct seg1{
vector<ll> sum, mi;
int n;
seg1(int _n = 0){
n = _n;
sum.resize(4 * n + 3, 0);
mi.resize(4 * n + 3, 0);
}
void upd(int p, ll c){
int i = 1, l = 1, r = n;
while(l < r){
int m = (l + r) >> 1;
if(p <= m){
i = i * 2;
r = m;
}
else{
i = i * 2 + 1;
l = m + 1;
}
}
sum[i] += c;
minimize(mi[i], sum[i]);
while(i){
i >>= 1;
sum[i] = sum[i * 2] + sum[i * 2 + 1];
mi[i] = min(mi[i * 2], sum[i * 2] + mi[i * 2 + 1]);
}
}
pair<ll, ll> get(int p){
pair<ll, ll> ans = make_pair(0, 0);
int i = 1, l = 1, r = n;
while(l < r){
int m = (l + r) >> 1;
if(p <= m){
i = i * 2;
r = m;
}
else{
ans.fi += sum[i * 2];
minimize(ans.se, mi[i * 2]);
i = i * 2 + 1;
l = m + 1;
}
}
ans.fi += sum[i];
minimize(ans.se, mi[i]);
return ans;
}
};
struct seg2{
vector<pair<ll, int>> it;
vector<ll> lazy;
int n;
void build(int i, int l, int r){
if(l == r){
it[i] = make_pair(0, l);
return;
}
int m = (l + r) >> 1;
build(i * 2, l, m);
build(i * 2 + 1, m + 1, r);
}
seg2(int _n = 0){
n = _n;
it.resize(4 * n + 3);
lazy.resize(4 * n + 3, 0);
build(1, 1, n);
}
void push(int i){
ll t = lazy[i];
lazy[i] = 0;
lazy[i * 2] += t;
lazy[i * 2 + 1] += t;
it[i * 2].fi += t;
it[i * 2 + 1].fi += t;
}
void upd(int i, int l, int r, int u, int v, ll c){
if(r < u || v < l) return;
if(u <= l && r <= v){
lazy[i] += c;
it[i].fi += c;
return;
}
push(i);
int m = (l + r) >> 1;
upd(i * 2, l, m, u, v, c);
upd(i * 2 + 1, m + 1, r, u, v, c);
it[i] = min(it[i * 2], it[i * 2 + 1]);
}
void upd(int u, int v, ll c){
upd(1, 1, n, u, v, c);
}
};
const int MAX = 250003;
int N, M, Q;
vector<pair<int, ll>> event[MAX], adds[MAX], ask[MAX], save[MAX];
int ans[MAX];
void solve(){
cin >> N >> M >> Q;
fen bit(Q);
seg1 it1(Q);
seg2 it2(N);
vector<vector<ll>> need;
for(int q=1; q<=Q; q++){
int t; cin >> t;
if(t == 1){
ll l, r, c, k;
cin >> l >> r >> c >> k;
need.push_back({l, r, c, k});
adds[l].push_back(make_pair(q, k));
adds[r + 1].push_back(make_pair(q, -k));
event[l].push_back(make_pair(q, k));
event[r + 1].push_back(make_pair(q, -k));
}
if(t == 2){
ll l, r, k;
cin >> l >> r >> k;
event[l].push_back(make_pair(q, -k));
event[r + 1].push_back(make_pair(q, k));
}
if(t == 3){
ll a, b;
cin >> a >> b;
ask[a].push_back(make_pair(q, b));
}
}
memset(ans, -1, sizeof ans);
for(int i=1; i<=N; i++){
for(auto o: event[i]){
it1.upd(o.fi, o.se);
}
for(auto o: adds[i]){
bit.upd(o.fi, o.se);
}
for(auto o: ask[i]){
pair<ll, ll> it = it1.get(o.fi);
ll num = it.fi - it.se;
// cout << o.fi << ' ' << o.se << ' ' << num << '\n';
if(num >= o.se){
save[i].push_back(make_pair(bit.get(o.fi) - num + o.se, o.fi));
}
else{
ans[o.fi] = 0;
}
}
sort(ALL(save[i]), greater<pair<ll, ll>>());
if(sz(save[i])){
it2.upd(i, i, save[i].back().fi);
}
else{
it2.upd(i, i, (ll)1e16);
}
}
for(auto o: need){
it2.upd(o[0], o[1], -o[3]);
while(it2.it[1].fi <= 0){
int i = it2.it[1].se;
ans[save[i].back().se] = o[2];
ll pr = save[i].back().fi;
save[i].pop_back();
if(sz(save[i])){
it2.upd(i, i, save[i].back().fi - pr);
}
else{
it2.upd(i, i, (ll)1e16 - pr);
}
}
}
for(int i=1; i<=Q; i++){
// cout << ans[i] << ' ';
if(ans[i] != -1){
cout << ans[i] << '\n';
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("deggraph.inp", "r", stdin);
// freopen("deggraph.out", "w", stdout);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
26204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
26204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
42184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
375 ms |
84196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
26204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
42508 KB |
Output is correct |
| 2 |
Correct |
94 ms |
44300 KB |
Output is correct |
| 3 |
Correct |
83 ms |
45712 KB |
Output is correct |
| 4 |
Correct |
60 ms |
41228 KB |
Output is correct |
| 5 |
Correct |
75 ms |
43444 KB |
Output is correct |
| 6 |
Correct |
84 ms |
45580 KB |
Output is correct |
| 7 |
Correct |
25 ms |
36212 KB |
Output is correct |
| 8 |
Correct |
25 ms |
35380 KB |
Output is correct |
| 9 |
Correct |
47 ms |
44116 KB |
Output is correct |
| 10 |
Correct |
53 ms |
40500 KB |
Output is correct |
| 11 |
Correct |
73 ms |
44752 KB |
Output is correct |
| 12 |
Correct |
75 ms |
44916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
26204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
26204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
