#include <vector>
#include <bits/stdc++.h>
#undef BALBIT
#define int ll
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define pb push_back
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#endif // BALBIT
struct state{
int L, R; // (-oo, L] maps to Lto, (L,R] maps to y+len, (R, oo) maps to Rto
int len;
int Lto, Rto;
int Lval, Rval; // Lval is Lval, R's value is y+Rval
pii eval(int y) { // {point to, cost}
if (y <= L) {
return {Lto, Lval};
}
if (y > R) {
return {Rto, y + Rval};
}
return {y+len, 0};
}
};
state base(int L, int R) {
return {L,R-1,1,L+1,R-1+1,0,-(R-1)};
}
state merge (state a, state b){
state re;
re.len = a.len + b.len;
// int oldL=0, oldR=0;
// bool eq = a.L == a.R;
if (b.L - a.len >= a.R) {
a.L = a.R;
}else if (b.R - a.len <= a.L) {
a.R = a.L;
}else{
MX(a.L, b.L - a.len);
MN(a.R, b.R - a.len);
}
{
pii ga = b.eval(a.L + a.len);
pii gb = b.eval(a.R + a.len);
re.Lto = ga.f, re.Lval = ga.s;
re.Rto = gb.f, re.Rval = gb.s - a.R;
}
re.L = a.L; re.R = a.R;
return re;
}
const int maxn = 3e5+5;
pii A[maxn];
state s[maxn*4];
void build(int o, int l, int r) {
if (l == r) {
s[o] = base(A[l].f, A[l].s);
return;
}
int mid = (l+r)/2;
build(o*2,l,mid); build(o*2+1,mid+1,r);
s[o] = merge(s[o*2], s[o*2+1]);
}
pii QU(int L, int R, int pt, int o, int l, int r) {
if (l > R || r < L) return {pt,0};
if (l >= L && r <= R) {
return s[o].eval(pt);
}
int mid = (l+r)/2;
pii gl = QU(L,R,pt,o*2,l,mid);
pii gr = QU(L,R,gl.f,o*2+1,mid+1,r);
gr.s += gl.s;
return gr;
}
void MO(int p, pii v, int o, int l, int r) {
if (l > p || r < p) return;
if (l==r) {
s[o] = base(v.f, v.s);
return;
}
int mid = (l+r)/2;
MO(p,v,o*2,l,mid); MO(p,v,o*2+1,mid+1,r);
s[o] = merge(s[o*2], s[o*2+1]);
}
struct query{
int l, r, t1, t2; // if l == -1, it's a modify operation on point r, range [t1,t2]
};
query ask[maxn];
int ans[maxn];
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
bug(1,2);
int n,q; cin>>n>>q;
REP(i,n-1) {
cin>>A[i].f>>A[i].s;
}
REP(i,q) {
int T; cin>>T;
if (T == 1) {
int p,s,e; cin>>p>>s>>e;
--p;
ask[i] = {-1, p, s, e};
}else{
int l,r,t1,t2;
cin>>l>>t1>>r>>t2;
--l; --r;
ask[i] = {l,r,t1,t2};
}
}
memset(ans, -1, sizeof ans);
REP(round, 2) {
build(1,0,n-1);
REP(i,q) {
query Q = ask[i];
if (Q.l == Q.r) {
ans[i] = max(0ll, Q.t1 - Q.t2);
}
if (Q.l < Q.r) {
if (Q.l == -1) {
MO(Q.r, make_pair(Q.t1, Q.t2), 1,0,n-1);
}else{
pii ha = QU(Q.l, Q.r-1, Q.t1, 1, 0, n-1);
bug(i, ha.f, ha.s);
int re = ha.s + max(0ll, ha.f - Q.t2);
ans[i] = re;
}
}
}
reverse(A, A+n-1);
for (query &qqq : ask) {
if (qqq.l == -1) {
qqq.r = n-qqq.r-2;
}else{
qqq.l = n-qqq.l-1;
qqq.r = n-qqq.r-1;
}
}
}
REP(i,q) if (ans[i] != -1) cout<<ans[i]<<endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
11988 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
817 ms |
77356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
11988 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
