#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
//typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
const int N = 250'010;
const ll inf = 1e18;
namespace beats {
struct node {
ll lzyadd, lzyaddmn;
ll mn, mn2;
} t[4*N];
int sz;
void up(int i, ll add, ll addmn) {
t[i].lzyadd += add;
t[i].mn += add;
t[i].mn2 += add;
t[i].lzyaddmn += addmn;
t[i].mn += addmn;
}
void ppg(int i) {
up(2*i+1, t[i].lzyadd, t[2*i+1].mn + t[i].lzyadd + t[i].lzyaddmn == t[i].mn? t[i].lzyaddmn: 0);
up(2*i+2, t[i].lzyadd, t[2*i+2].mn + t[i].lzyadd + t[i].lzyaddmn == t[i].mn? t[i].lzyaddmn: 0);
t[i].lzyadd = 0;
t[i].lzyaddmn = 0;
}
void merge(int i) {
node &v = t[i], &l = t[2*i+1], &r = t[2*i+2];
v.mn = min(l.mn, r.mn);
if (l.mn < r.mn)
v.mn2 = min(l.mn2, r.mn);
if (l.mn > r.mn)
v.mn2 = min(l.mn, r.mn2);
if (l.mn == r.mn)
v.mn2 = min(l.mn2, r.mn2);
}
void init(int n) {
sz = n;
Loop (i,0,4*sz) {
t[i].lzyadd = 0;
t[i].lzyaddmn = 0;
t[i].mn = 0;
t[i].mn2 = inf;
}
}
void add(int l, int r, ll x, int i, int b, int e) {
if (l <= b && e <= r) {
up(i, x, 0);
return;
}
if (r <= b || e <= l)
return;
ppg(i);
add(l, r, x, 2*i+1, b, (b+e)/2);
add(l, r, x, 2*i+2, (b+e)/2, e);
merge(i);
}
void mvup(int i, int b, int e) {
if (t[i].mn >= 0)
return;
if (t[i].mn2 > 0) {
up(i, 0, -t[i].mn);
return;
}
ppg(i);
mvup(2*i+1, b, (b+e)/2);
mvup(2*i+2, (b+e)/2, e);
merge(i);
}
void add(int l, int r, ll x) {
add(l, r, x, 0, 0, sz);
mvup(0, 0, sz);
}
ll get(int p, int i, int b, int e) {
if (e-b == 1)
return t[i].mn;
ppg(i);
if (p < (b+e)/2)
return get(p, 2*i+1, b, (b+e)/2);
else
return get(p, 2*i+2, (b+e)/2, e);
}
ll get(int p) { return get(p, 0, 0, sz); }
}
namespace seg {
struct node {
ll cnt, cachev;
int l, r;
int cache;
} nd[(1<<28)/sizeof(node)];
int nxt = 1;
vector<pair<int,int>> rts;
int sz;
void init(int n) {
sz = n;
rts = {{0,-1}};
}
int add(int t, int l, int r, ll x, int b, int e) {
int ans = nxt++;
if (l <= b && e <= r) {
nd[ans].cnt = nd[t].cnt + x;
nd[ans].l = nd[t].l;
nd[ans].r = nd[t].r;
return ans;
}
nd[ans] = nd[t];
if (l < (b+e)/2)
nd[ans].l = add(nd[t].l, l, r, x, b, (b+e)/2);
if ((b+e)/2 < r)
nd[ans].r = add(nd[t].r, l, r, x, (b+e)/2, e);
return ans;
}
ll get(int t, int p, int b, int e) {
if (!t)
return 0;
if (e-b == 1)
return nd[t].cnt;
if (nd[t].cache == p+1)
return nd[t].cachev;
ll ans;
if (p < (b+e)/2)
ans = nd[t].cnt + get(nd[t].l, p, b, (b+e)/2);
else
ans = nd[t].cnt + get(nd[t].r, p, (b+e)/2, e);
nd[t].cachev = ans;
nd[t].cache = p+1;
return ans;
}
void add(int l, int r, ll x, int c) {
int rt = rts.back().first;
int rt2 = add(rt, l, r, x, 0, sz);
rts.push_back({rt2, c});
}
ll get(int p) { return get(rts.back().first, p, 0, sz); }
int bin(int p, ll i) {
int l = 1, r = rts.size()-1;
while (l < r) {
int m = (l+r)/2;
if (get(rts[m].first, p, 0, sz) > i)
r = m;
else
l = m+1;
}
return rts[l].second;
}
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int n, m, q;
cin >> n >> m >> q;
seg::init(n);
beats::init(n);
Loop (i,0,q) {
int t;
cin >> t;
if (t == 1) {
int l, r, c, k;
cin >> l >> r >> c >> k;
--l;
seg::add(l, r, k, c);
beats::add(l, r, k);
}
if (t == 2) {
int l, r, k;
cin >> l >> r >> k;
--l;
beats::add(l, r, -k);
}
if (t == 3) {
ll a, b;
cin >> a >> b;
--a; --b;
ll cur = beats::get(a);
ll tot = seg::get(a);
b += tot - cur;
if (b >= tot)
cout << "0\n";
else
cout << seg::bin(a, b) << '\n';
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
83 ms |
22380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
629 ms |
142996 KB |
Output is correct |
| 2 |
Correct |
481 ms |
114856 KB |
Output is correct |
| 3 |
Correct |
675 ms |
157672 KB |
Output is correct |
| 4 |
Correct |
638 ms |
171692 KB |
Output is correct |
| 5 |
Correct |
637 ms |
164748 KB |
Output is correct |
| 6 |
Correct |
958 ms |
225840 KB |
Output is correct |
| 7 |
Correct |
62 ms |
3912 KB |
Output is correct |
| 8 |
Correct |
72 ms |
5108 KB |
Output is correct |
| 9 |
Execution timed out |
1098 ms |
200556 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
171 ms |
46568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
