#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const ll inf = numeric_limits<ll> :: max();
struct STB{
struct data{
ll min, min2, sum;
int cnt;
};
vector<data> t;
vector<ll> p;
// a[i] += x (l <= i <= r)
// a[i] = max(a[i], x) (l <= i <= r)
// ? a[i]
int n;
STB(int ns){
n = ns;
t.resize(4 * n);
for (int i = 1; i < t.size(); i++) t[i].min2 = inf;
p.resize(4 * n);
}
void merge(int& v, int& vv){
t[v].min = min(t[vv].min, t[vv + 1].min);
if (t[vv].min == t[vv + 1].min){
t[v].min2 = min(t[vv].min2, t[vv + 1].min2);
}
else {
if (t[vv].min < t[vv + 1].min){
t[v].min2 = min(t[vv + 1].min, t[vv].min2);
}
else {
t[v].min2 = min(t[vv].min, t[vv + 1].min2);
}
}
t[v].cnt = 0;
if (t[vv].min == t[v].min) t[v].cnt += t[vv].cnt;
if (t[vv + 1].min == t[v].min) t[v].cnt += t[vv + 1].cnt;
t[v].sum = t[vv].sum + t[vv + 1].sum;
}
void apply_a(int v, ll& x, int len){
if (!x) return;
t[v].sum += x * len;
t[v].min += x;
if (t[v].min2 != inf) t[v].min2 += x;
p[v] += x;
}
void apply_m(int v, ll& x){
if (t[v].min >= x) return;
t[v].sum += (x - t[v].min) * t[v].cnt;
t[v].min = x;
}
void push(int& v, int& vv, int& tl, int& tm, int& tr){
apply_a(vv, p[v], tm - tl + 1);
apply_a(vv + 1, p[v], tr - tm);
p[v] = 0;
apply_m(vv, t[v].min);
apply_m(vv + 1, t[v].min);
}
void add(int v, int tl, int tr, int& l, int& r, ll& x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
apply_a(v, x, tr - tl + 1);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push(v, vv, tl, tm, tr);
add(vv, tl, tm, l, r, x);
add(vv + 1, tm + 1, tr, l, r, x);
merge(v, vv);
}
void add(int l, int r, ll x){
add(1, 1, n, l, r, x);
}
void chmax(int v, int tl, int tr, int& l, int& r, ll& x){
if (l > tr || r < tl || t[v].min >= x) return;
if (l <= tl && tr <= r && t[v].min2 > x){
apply_m(v, x);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push(v, vv, tl, tm, tr);
chmax(vv, tl, tm, l, r, x);
chmax(vv + 1, tm + 1, tr, l, r, x);
merge(v, vv);
}
void chmax(int l, int r, ll x){
chmax(1, 1, n, l, r, x);
}
ll get(int v, int tl, int tr, int& p){
if (tl == tr){
return t[v].min;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push(v, vv, tl, tm, tr);
if (p <= tm){
return get(vv, tl, tm, p);
}
return get(vv + 1, tm + 1, tr, p);
}
ll get(int p){
return get(1, 1, n, p);
}
};
struct ST{
struct node{
ll sum, max_suf;
};
using pni = pair<node, int>;
vector<node> t;
node null;
int n;
ST(int ns){
n = ns;
t.resize(4 * n);
null = {0, 0};
}
node merge(node x, node y){
return {x.sum + y.sum, max(y.max_suf, x.max_suf + y.sum)};
}
void upd(int v, int tl, int tr, int& p, int& k){
if (tl == tr){
t[v] = {k, k};
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
if (p <= tm){
upd(vv, tl, tm, p, k);
}
else {
upd(vv + 1, tm + 1, tr, p, k);
}
t[v] = merge(t[vv], t[vv + 1]);
}
void upd(int p, int k){
upd(1, 1, n, p, k);
}
node get(int v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return null;
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2, vv = 2 * v;
return merge(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
}
ll get(int l, int r){
return get(1, 1, n, l, r).max_suf;
}
};
struct ST1{
vector<ll> t;
int n;
ST1(int ns){
n = ns;
t.resize(4 * n);
}
void upd(int v, int tl, int tr, int& p, int& k){
if (tl == tr){
t[v] = k;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
if (p <= tm){
upd(vv, tl, tm, p, k);
}
else {
upd(vv + 1, tm + 1, tr, p, k);
}
t[v] = t[vv] + t[vv + 1];
}
void upd(int p, int k){
upd(1, 1, n, p, k);
}
ll get(int v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return 0;
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2, vv = 2 * v;
return get(vv, tl, tm, l, r) + get(vv + 1, tm + 1, tr, l, r);
}
ll get(int l, int r){
return get(1, 1, n, l, r);
}
int get_p(int r, ll k){
int bl = 1, br = r;
while (bl + 1 < br){
int m = (bl + br) / 2;
if (get(1, m) >= k){
br = m;
}
else {
bl = m + 1;
}
}
if (get(1, bl) >= k) br = bl;
return br;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, q; cin>>n>>m>>q;
vector<pii> st[n + 2];
vector<array<ll, 3>> qs[n + 1];
vector<int> col(q + 1);
STB TT(n);
for (int tt = 1; tt <= q; tt++){
int type; cin>>type;
if (type == 1){
int l, r, c, k; cin>>l>>r>>c>>k;
st[l].pb({tt, k});
st[r + 1].pb({tt, 0});
TT.add(l, r, k);
col[tt] = c;
}
else if (type == 2){
int l, r, k; cin>>l>>r>>k;
TT.add(l, r, -k);
TT.chmax(1, n, 0);
st[l].pb({tt, -k});
st[r + 1].pb({tt, 0});
}
else {
int a, b; cin>>a>>b;
qs[a].pb({tt, TT.get(a), b});
}
}
ST T(q);
ST1 Ts(q);
vector<int> out(q + 1, -1);
for (int i = 1; i <= n; i++){
for (auto [j, k]: st[i]){
T.upd(j, k);
if (k >= 0) Ts.upd(j, k);
}
for (auto [j, cc, b]: qs[i]){
ll cur = T.get(1, j);
if (cur != cc) return 1;
if (b > cur){
out[j] = 0;
continue;
}
else {
out[j] = 1;
continue;
}
b = Ts.get(1, j) - cur + b;
out[j] = col[Ts.get_p(j, b)];
}
}
for (int i = 1; i <= q; i++){
if (out[i] != -1){
cout<<out[i]<<"\n";
}
}
}
Compilation message
foodcourt.cpp: In constructor 'STB::STB(int)':
foodcourt.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<STB::data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (int i = 1; i < t.size(); i++) t[i].min2 = inf;
| ~~^~~~~~~~~~
| # |
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 |
Incorrect |
98 ms |
22612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
75212 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 |
Incorrect |
18 ms |
20432 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 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
