This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
const int inf=1e9;
vector<pair<int,int> > gg[2];
struct ST{
int tp;
struct no{
int ax,ay,bx;
// <=ax : ay
// >=bx : by=bx+(ay-ax)
int dx,dy;
// <=dx : dy
// >=dx : linear
};
vector<no> st;
pair<int,int> get(no& a,int x){
pair<int,int> ret;
if(x<=a.ax){
ret.fs=a.ay;
}
else if(x>=a.bx){
ret.fs=a.bx+a.ay-a.ax;
}
else{
ret.fs=a.ay+(x-a.ax);
}
if(x<=a.dx){
ret.sc=a.dy;
}
else{
ret.sc=a.dy+x-a.dx;
}
return ret;
}
void upd(int v,int l,int r){
st[v].ax=l;
st[v].ay=l+1;
st[v].bx=r;
st[v].dx=r;
st[v].dy=0;
}
void pull(int v){
auto p=st[2*v+1],q=st[2*v+2];
if(get(q,p.ay).fs==get(q,p.bx+p.ay-p.ax).fs){
st[v].ax=st[v].bx=0;
st[v].ay=get(q,p.ay).fs;
}
else{
st[v].ax=p.ax+max(0ll,q.ax-p.ay);
st[v].ay=get(q,get(p,st[v].ax).fs).fs;
st[v].bx=p.bx-max(0ll,p.bx+p.ay-p.ax-q.bx);
}
int c=get(p,0).sc+get(q,get(p,0).fs).sc,d=get(p,inf).sc+get(q,get(p,inf).fs).sc;
st[v].dx=inf-(d-c);
st[v].dy=c;
}
void build(int v,int L,int R){
if(L==R){
upd(v,gg[tp][L].fs,gg[tp][L].sc);
return;
}
int m=(L+R)/2;
build(2*v+1,L,m);
build(2*v+2,m+1,R);
pull(v);
}
void print(int v){
cout << v << ":" << "\n";
cout << st[v].ax << " " << st[v].ay << " " << st[v].bx << "\n";
cout << st[v].dx << " " << st[v].dy << "\n\n";
}
void init(int x){
st.resize(4*x);
build(0,0,x-1);
}
void update(int v,int L,int R,int p,int l,int r){
if(L==R){
upd(v,l,r);
return;
}
int m=(L+R)/2;
if(p<=m){
update(2*v+1,L,m,p,l,r);
}
else{
update(2*v+2,m+1,R,p,l,r);
}
pull(v);
}
pair<int,int> query(int v,int L,int R,int l,int r,int x){
if(L==l && R==r){
return get(st[v],x);
}
int m=(L+R)/2;
if(r<=m){
return query(2*v+1,L,m,l,r,x);
}
else if(l>m){
return query(2*v+2,m+1,R,l,r,x);
}
else{
auto h=query(2*v+1,L,m,l,m,x);
auto y=query(2*v+2,m+1,R,m+1,r,h.fs);
return {y.fs,y.sc+h.sc};
}
}
}st[2];
signed main(){
AquA;
int n,q;
cin >> n >> q;
n--;
gg[0].resize(n);
gg[1].resize(n);
for(int i=0;i<n;i++){
cin >> gg[0][i].fs >> gg[0][i].sc;
gg[0][i].sc--;
}
gg[1]=gg[0];
reverse(gg[1].begin(),gg[1].end());
st[0].tp=0;
st[1].tp=1;
st[0].init(n);
st[1].init(n);
for(int i=0;i<4*n;i++){
//st[1].print(i);
}
//cout << st.st[0].ax << " " << st.st[0].ay << " " << st.st[0].bx << " " << st.st[0].dx << " " << st.st[0].dy << '\n';
//cout << st.get(st.st[0],3).fs << " " << st.get(st.st[0],3).sc << "\n";
for(int i=0;i<q;i++){
int t;
cin >> t;
if(t==1){
int a,l,r;
cin >> a >> l >> r;
a--;
r--;
st[0].update(0,0,n-1,a,l,r);
st[1].update(0,0,n-1,n-a-1,l,r);
}
else{
int a,b,c,d;
cin >> a >> b >> c >> d;
if(a==c){
cout << max(0ll,b-d) << "\n";
continue;
}
if(a<c){
a--;
c--;
c--;
auto h=st[0].query(0,0,n-1,a,c,b);
cout << h.sc+(max(0ll,h.fs-d)) << "\n";
}
else{
a--;
c--;
a=n-a;
c=n-c;
c--;
//cout << a << " " << c << endl;
auto h=st[1].query(0,0,n-1,a,c,b);
cout << h.sc+(max(0ll,h.fs-d)) << "\n";
}
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |