#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 70000;
const int B = 266;
int n, m, q;
deque<pair<int, ll>> g[N];
struct obj {
ll pos, c, k;
};
deque<obj> que[N], bl_q[N / B];
void add(deque<obj> &q, int c, ll k) {
if(q.empty()) q.push_back({0, c, k});
else q.push_back({(q.back().pos + q.back().k), c, k});
}
ll find(deque<obj> &q, ll b) {
if(q.empty() || q.back().pos + q.back().k <= b || b < 0) return 0;
int l = -1, r = (int)q.size();
while(r - l > 1) {
int mid = (l + r) / 2;
if(b < q[mid].pos) r = mid;
else l = mid;
}
return q[l].c;
}
void push(int bl) {
for(int i = bl * B; i < (bl + 1) * B; i++) {
for(obj z : bl_q[bl])
add(que[i], z.c, z.k);
}
bl_q[bl].clear();
}
ll answer(int a, ll b) {
b--;
ll ans = find(que[a], b);
if(ans) return ans;
if(!que[a].empty()) b -= que[a].back().pos + que[a].back().k;
return find(bl_q[a / B], b);
}
vector<vector<ll>> qr;
void solve() {
for(auto g : qr) {
if(g[0] == 1) {
ll l, r, c, k;
l = g[1], r = g[2], c = g[3], k = g[4];
while(l <= r) {
bool flag = (l % B == 0 && l + B - 1 <= r);
if(flag) add(bl_q[l / B], c, k), l += B;
else {
if(!bl_q[l / B].empty()) push(l / B);
add(que[l], c, k);
l++;
}
}
}
if(g[0] == 3) {
ll a, b;
a = g[1], b = g[2];
cout << answer(a, b) << '\n';
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m >> q;
// if(n <= 2000 && q <= 2000) {
// for(int i = 0; i < q; i++) {
// int t;
// cin >> t;
// if(t == 1) {
// ll l, r, c, k;
// cin >> l >> r >> c >> k;
// for(int j = l; j <= r; j++) {
// g[j].push_back({c, k});
// }
// }
// if(t == 2) {
// ll l, r, k;
// cin >> l >> r >> k;
// for(int j = l; j <= r; j++) {
// int p = k;
// while(!g[j].empty() && g[j].front().second <= p) {
// p -= g[j].front().second;
// g[j].pop_front();
// }
// if(!g[j].empty())
// g[j][0].second -= p;
// }
// }
// if(t == 3) {
// ll a, b;
// cin >> a >> b;
// int ans = 0;
// for(auto [c, k] : g[a]) {
// if(b > k) b -= k;
// else {ans = c; break;}
// }
// cout << ans << '\n';
// }
// }
// return 0;
// }
bool flag = 1;
for(int i = 0; i < q; i++) {
int t;
cin >> t;
ll l, r, c, k, a, b;
if(t == 1) {
cin >> l >> r >> c >> k;
qr.push_back({t, l, r, c, k});
}
if(t == 2) {
cin >> l >> r >> k;
flag = 0;
qr.push_back({t, l, r, k});
}
if(t == 3) {
cin >> a >> b;
qr.push_back({t, a, b});
}
}
if(flag) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
93684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
93684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
97948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
113720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
93684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
410 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
93684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
93684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
