#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;
int n, m, q;
int res[MAX_N], cid[MAX_N];
bool is_leave[MAX_N];
// position, delta
vector<pair<int,ll>> 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) {
tg = 0;
mn = min(a.mn, b.mn);
pos = a.mn == mn ? a.pos : b.pos;
}
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;
// for (int i = n-1;i > 0;--i)
// upd(i);
}
void pa(int j) { for (int i = 20;i >= 0;--i) push(j>>i); }
void add(int l, int r, ll v) {
assert(r == q);
int sl = l+=n, sr = r+=n;
pa(l), pa(r-1);
for (;l < r;l>>=1, r>>=1) {
if (l&1) val[l++] += v;
if (r&1) val[--r] += v;
}
for (--sr;sl>>=1, sr>>=1;)
upd(sl), upd(sr);
}
void push(int i) {
if (i >= n) return;
ll &t = val[i].tg;
val[i<<1] += t, val[i<<1|1] += t;
t = 0;
}
void upd(int i) {
if (i >= n) return;
push(i);
val[i] = node(val[i<<1], val[i<<1|1]);
}
pair<ll,ll> qmn(int l, int r) {
l += n, r += n;
pa(l), pa(r-1);
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());
}
assert(res.first < inf);
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];
}
assert(k > 0);
return res + 1;
}
};
struct sss {
vector<ll> val;
int n;
sss (int n) : n(n) {
val.resize(n);
}
void add(int l, int r, ll v) {
for (;l < r;++l)
val[l] += v;
}
pair<ll,ll> qmn(int l, int r) {
pair<ll,ll> res {inf, n};
for (;l < r;++l)
chmin(res, make_pair(val[l], (ll)l));
return res;
}
};
void solve() {
//sss tree(q);
sgt tree(q);
bit t1(q + 10), t2(q + 10);
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 {
assert(cid[j]);
t1.add(j, d);
}
}
for (auto [t, k] : allq[i]) {
auto [v, p] = tree.qmn(0, t);
assert(p == 0 || is_leave[p]);
assert(p < t);
ll rk = t1.qry(p) + k + t2.qry(p+1, t);
//assert(p == 0 || t1.qry(p) == t1.qry(p-1));
assert(t1.qry(p) - t2.qry(p) == v);
if (t1.qry(t) < rk) {
res[t] = 0;
continue;
}
int ind = t1.kth(rk);
assert(ind < t);
res[t] = cid[ind];
assert(cid[ind] >= 1 && cid[ind] <= m);
}
}
}
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 |
Runtime error |
28 ms |
29380 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
29380 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
44268 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
242 ms |
82776 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
29380 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
20892 KB |
Output is correct |
| 2 |
Correct |
130 ms |
21524 KB |
Output is correct |
| 3 |
Correct |
134 ms |
21648 KB |
Output is correct |
| 4 |
Correct |
90 ms |
19564 KB |
Output is correct |
| 5 |
Correct |
128 ms |
20596 KB |
Output is correct |
| 6 |
Correct |
148 ms |
21632 KB |
Output is correct |
| 7 |
Correct |
63 ms |
19960 KB |
Output is correct |
| 8 |
Correct |
72 ms |
19596 KB |
Output is correct |
| 9 |
Correct |
90 ms |
20936 KB |
Output is correct |
| 10 |
Correct |
97 ms |
19416 KB |
Output is correct |
| 11 |
Correct |
122 ms |
21300 KB |
Output is correct |
| 12 |
Correct |
133 ms |
21424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
29380 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
29380 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
