#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
const ll inf = 1ll << 60;
#define int ll
int n, m, q;
int res[MAX_N], cid[MAX_N];
bool is_leave[MAX_N];
// position, delta
vector<pair<int,int>> rec[MAX_N];
// time, k
vector<pair<int,ll>> allq[MAX_N];
struct sgt {
struct node {
ll mn, pos, tg;
void operator += (ll v) {
mn += v, tg += v;
}
node (node a, node b) {
mn = min(a.mn, b.mn);
if (a.mn == mn) pos = a.pos;
else pos = b.pos;
tg = 0;
}
node () : mn(0), pos(0), tg(0) {}
pair<ll,ll> get() { return make_pair(mn, pos); }
};
int n;
vector<node> val;
sgt(int n) : n(n) {
val.resize(n<<1);
for (int i = 0;i < n;++i)
val[i+n].pos = i;
}
void add(int l, int r, ll v) {
int sl = l+=n, sr = r+=n;
for (;l < r;l>>=1, r>>=1) {
if (l&1) val[l++] += v;
if (r&1) val[--r] += v;
}
for (;sl>>=1, sr>>=1;)
upd(sl), upd(sr);
}
void upd(int i) {
if (i >= n) return;
ll &t = val[i].tg;
val[i<<1] += t, val[i<<1|1] += t;
val[i] = node(val[i<<1], val[i<<1|1]);
}
pair<ll,ll> qmn(int l, int r) {
l += n, r += n;
for (int i = 19;i > 0;--i) upd(l>>i), upd(r>>i);
pair<ll,ll> res {inf, n};
for (;l < r;l>>=1, r>>=1) {
if (l&1) chmin(res, val[l++].get());
if (r&1) chmin(res, val[--r].get());
}
return res;
}
};
// t1 for +
// t2 for -
struct bit {
int n;
vector<ll> val;
bit (int n) : n(n) {
val.resize(n);
}
void add(int i, ll v) {
for (;i < n;i += i&-i)
val[i] += v;
}
ll qry(int i) {
ll res = 0;
for (;i;i^=i&-i) res += val[i];
return res;
}
ll qry(int l, int r) { return qry(r) - qry(l-1); }
int kth(ll k) {
int res = 0;
for (int i = 1<<19;i > 0;i>>=1) {
if ((i|res) >= n || k <= val[res|i]) continue;
assert(k > val[res|i]);
k -= val[res|=i];
}
return res + 1;
}
};
void solve() {
bit t1(q + 10), t2(q + 10);
sgt tree(q);
for (int i = 1;i <= n;++i) {
for (auto [j, d] : rec[i]) {
tree.add(j, q, d);
if (is_leave[j])
t2.add(j, -d);
else
t1.add(j, d);
}
for (auto [t, k] : allq[i]) {
auto [v, p] = tree.qmn(0, t);
ll rk = t1.qry(p) + k + t2.qry(p+1, t);
if (t1.qry(t) < rk) {
res[t] = 0;
continue;
}
int ind = t1.kth(rk);
//DE(t, k, v, p, rk, ind, cid[ind]);
//DE(t1.qry(ind), rk, t1.qry(ind+1));
assert(ind < t);
res[t] = ind >= t ? 0 : cid[ind];
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> q; ++q;
fill(res, res + q, -1);
for (ll t, l, r, k, i = 1;i < q;++i) {
cin >> t;
if (t == 1) {
cin >> l >> r >> cid[i] >> k;
rec[l].pb(i, k);
rec[r+1].pb(i,-k);
}
if (t == 2) {
cin >> l >> r >> k;
is_leave[i] = true;
rec[l].pb(i, -k);
rec[r+1].pb(i, k);
}
if (t == 3) {
cin >> l >> k;
allq[l].pb(i, k);
}
}
solve();
for (int i = 0;i < q;++i) {
if (res[i] == -1) continue;
cout << res[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
22708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
638 ms |
43300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
21912 KB |
Output is correct |
| 2 |
Correct |
142 ms |
22536 KB |
Output is correct |
| 3 |
Correct |
179 ms |
22676 KB |
Output is correct |
| 4 |
Correct |
86 ms |
20368 KB |
Output is correct |
| 5 |
Correct |
99 ms |
21624 KB |
Output is correct |
| 6 |
Correct |
118 ms |
22664 KB |
Output is correct |
| 7 |
Correct |
62 ms |
20956 KB |
Output is correct |
| 8 |
Correct |
63 ms |
20592 KB |
Output is correct |
| 9 |
Correct |
102 ms |
21964 KB |
Output is correct |
| 10 |
Correct |
87 ms |
20272 KB |
Output is correct |
| 11 |
Correct |
96 ms |
22324 KB |
Output is correct |
| 12 |
Correct |
127 ms |
22348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
