| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 865300 | guagua0407 | Bitaro, who Leaps through Time (JOI19_timeleap) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
struct node{
ll s1,s2,e1,e2,c1,c2,sz;
};
const int mxn=3e5+5;
vector<vector<node>> segtree(2,vector<node>(mxn*4));
int n,q;
ll L[mxn],R[mxn];
node trash;
node merge(node a,node b){
if(a.sz==-1) return b;
if(b.sz==-1) return a;
node ans;
ans.sz=a.sz+b.sz;
ans.s1=a.s1;
ans.s2=a.s2;
{
ans.c1=a.c1;
if(a.e1>b.s1){
ans.c1+=b.c1+(a.e1-b.s1);
ans.e1=b.e1;
}
else if(a.e1>=b.s2){
int dif=b.c1-b.c2;
ans.c1+=b.c2+max(0ll,dif-(b.s1-a.e1));
int res=a.e1+b.sz;
if(res>b.e1){
ans.e1=b.e1;
}
else{
ans.e1=max(res,b.e2);
}
}
else{
ans.c1+=b.c2;
ans.e1=b.e2;
}
}
{
ans.c2=a.c2;
if(a.e2>b.s1){
ans.c2+=b.c1+(a.e2-b.s1);
ans.e2=b.e1;
}
else if(a.e2>=b.s2){
int dif=b.c1-b.c2;
ans.c2+=b.c2+max(0ll,dif-(b.s1-a.e2));
int res=a.e2+b.sz;
if(res>b.e1){
ans.e2=b.e1;
}
else{
ans.e2=max(res,b.e2);
}
}
else{
ans.c2+=b.c2;
ans.e2=b.e2;
}
}
return ans;
}
void build(int id,int l=1,int r=n-1,int v=1){
if(l==r){
segtree[id][v].s1=R[l]-1;
segtree[id][v].s2=L[l];
segtree[id][v].e1=R[l];
segtree[id][v].e2=L[l]+1;
segtree[id][v].c1=segtree[id][v].c2=0;
segtree[id][v].sz=1;
return;
}
int mid=(l+r)/2;
build(id,l,mid,v*2);
build(id,mid+1,r,v*2+1);
segtree[id][v]=merge(segtree[id][v*2],segtree[id][v*2+1]);
}
void update(int id,int pos,int s,int e,int l=1,int r=n-1,int v=1){
if(l==r){
segtree[id][v].s1=e-1;
segtree[id][v].s2=s;
segtree[id][v].e1=e;
segtree[id][v].e2=s+1;
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(id,pos,s,e,l,mid,v*2);
else update(id,pos,s,e,mid+1,r,v*2+1);
segtree[id][v]=merge(segtree[id][v*2],segtree[id][v*2+1]);
}
node query(int id,int tl,int tr,int l=1,int r=n-1,int v=1){
if(r<tl or tr<l){
return trash;
}
if(tl<=l and r<=tr){
return segtree[id][v];
}
int mid=(l+r)/2;
return merge(query(id,tl,min(mid,tr),l,mid,v*2),query(id,max(mid+1,tl),tr,mid+1,r,v*2+1));
}
signed main() {_
trash.sz=-1;
cin>>n>>q;
for(int i=1;i<n;i++){
cin>>L[i]>>R[i];
}
build(0);
reverse(L+1,L+n);
reverse(R+1,R+n);
build(1);
reverse(L+1,L+n);
reverse(R+1,R+n);
for(int i=0;i<q;i++){
int t;
cin>>t;
if(t==1){
ll p,s,e;
cin>>p>>s>>e;
update(0,p,s,e);
update(1,n-p,s,e);
}
else{
ll a,b,c,d;
cin>>a>>b>>c>>d;
if(a==c){
cout<<max(0ll,b-d)<<'\n';
continue;
}
node tmp;
if(a<c){
tmp=query(0,a,c-1);
}
else{
a=n-a+1;
c=n-c+1;
//swap(b,d);
tmp=query(1,a,c-1);
}
/*cout<<tmp.sz<<'\n';
cout<<tmp.s1<<' '<<tmp.s2<<'\n';
cout<<tmp.e1<<' '<<tmp.e2<<'\n';
cout<<tmp.c1<<' '<<tmp.c2<<'\n';*/
ll ans=0;
int fin;
if(b>tmp.s1){
ans+=tmp.c1+(b-tmp.s1);
fin=tmp.e1;
}
else if(b>=tmp.s2){
ll dif=tmp.c1-tmp.c2;
ans+=tmp.c2+max(0ll,dif-(tmp.s1-b));
ll res=b+tmp.sz;
if(res>tmp.e1){
fin=tmp.e1;
}
else{
fin=max(res,tmp.e2);
}
}
else{
ans+=tmp.c2;
fin=tmp.e2;
}
cout<<ans+max(0ll,fin-d)<<'\n';;
}
}
return 0;
}
//maybe its multiset not set