/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2.5e5 + 50;
ll n, m, q, out[N];
vector<pll> qr[N];
vector<pll> bd[N<<2];
vector<pair<ll, pll>> vc[N<<2];
pll fen[N];
void join(ll l, ll r, ll c, ll k, ll tim, ll u=1, ll tl=1, ll tr=n) {
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) {
vc[u].push_back({tim, {k, c}});
return;
}
ll md = (tl+tr)/2;
ll lc = u<<1;
ll rc = u<<1|1;
join(l, r, c, k, tim, lc, tl, md), join(l, r, c, k, tim, rc, md+1, tr);
}
void leave(ll l, ll r, ll k, ll tim, ll u=1, ll tl=1, ll tr=n) {
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) {
bd[u].push_back({tim, k});
return;
}
ll md = (tl+tr)/2;
ll lc = u<<1;
ll rc = u<<1|1;
leave(l, r, k, tim, lc, tl, md), leave(l, r, k, tim, rc, md+1, tr);
}
void service(ll id, ll x, ll tim, ll u=1, ll tl=1, ll tr=n) {
if (id < tl || tr < id) return;
if (tl == tr) {
qr[tl].push_back({tim, x});
return;
}
ll md = (tl+tr)/2;
ll lc = u<<1;
ll rc = u<<1|1;
service(id, x, tim, lc, tl, md), service(id, x, tim, rc, md+1, tr);
}
void upd(ll i, ll x) {
if (!i) return fen[i].F += x, void();
for (; i < N; i += i&-i) {
fen[i].F += x;
}
}
ll get(ll x) {
ll id = 0;
x -= fen[0].F;
for (ll k = 18; k >= 0; k--) {
if (id+(1<<k) < N && fen[id^(1<<k)].F < x) {
id ^= (1<<k);
x -= fen[id].F;
}
}
id++;
return id;
}
void dfs(ll u=1, ll tl=1, ll tr=n) {
for (pll x: bd[u]) {
upd(0, x.S);
}
for (pair<ll, pll> x:vc[u]) {
fen[x.F].S = x.S.S;
upd(x.F, x.S.F);
}
if (tl == tr) {
for (pll x:qr[tl]) {
ll id = get(x.S);
cerr << "OK " << x.F << ' ' << x.S << ' ' << id << endl;
out[x.F] = (id < x.F? fen[id].S : 0);
}
}
ll md = (tl+tr)/2;
ll lc = u<<1;
ll rc = u<<1|1;
if (tl < tr) dfs(lc, tl, md), dfs(rc, md+1, tr);
for (pair<ll, pll> x:vc[u]) {
fen[x.F].S = 0;
upd(x.F, -x.S.F);
}
reverse(bd[u].begin(), bd[u].end());
for (pll x: bd[u]) {
upd(0, x.S);
}
}
void solve() {
cin >> n >> m >> q;
for (ll i = 1; i <= q; i++) {
out[i] = -1;
ll t, l, r, k, c, id, x;
cin >> t;
if (t == 1) {
cin >> l >> r >> c >> k;
join(l, r, c, k, i);
}
if (t == 2) {
cin >> l >> r >> k;
leave(l, r, k, i);
}
if (t == 3) {
cin >> id >> x;
service(id, x, i);
}
}
dfs();
for (ll i = 1; i <= q; i++) {
if (out[i] < 0) continue;
cout << out[i] << endl;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
53472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
53472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
299 ms |
65644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1082 ms |
132040 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
53472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
70384 KB |
Output is correct |
| 2 |
Correct |
392 ms |
71892 KB |
Output is correct |
| 3 |
Correct |
410 ms |
72360 KB |
Output is correct |
| 4 |
Correct |
285 ms |
67412 KB |
Output is correct |
| 5 |
Correct |
388 ms |
70580 KB |
Output is correct |
| 6 |
Correct |
411 ms |
73252 KB |
Output is correct |
| 7 |
Correct |
284 ms |
58088 KB |
Output is correct |
| 8 |
Correct |
277 ms |
57720 KB |
Output is correct |
| 9 |
Correct |
379 ms |
59040 KB |
Output is correct |
| 10 |
Correct |
271 ms |
68868 KB |
Output is correct |
| 11 |
Correct |
384 ms |
75916 KB |
Output is correct |
| 12 |
Correct |
384 ms |
75960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
53472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
53472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
