Submission #876202

#	Time	Username	Problem	Language	Result	Execution time	Memory
876202		winter0101	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	597 ms	77112 KiB

timeleap

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int inf=1e9;
struct node{
int type,l,r;
long long cost;
};
node operator + (const node &p,const node &q){
node r;
r.cost=p.cost+q.cost;
//need to divide into 2 types because type 1 will be 2 interval length 1 and type 0 will be interval [l,r]
if (!p.type&&!q.type){//both in case 1
if (max(p.l,q.l)<=min(p.r,q.r)){//case 1 again
r.l=max(p.l,q.l);
r.r=min(p.r,q.r);
r.type=0;
//no cost need
}
else {
//now the node will be 2 interval length 1 is [r.l,r.l] and [r.r,r.r]
if (p.l>q.r){//case 3
r.cost+=p.l-q.r;
r.l=p.l,r.r=q.r;
r.type=1;//no more intersect
}
else {//case 2
r.type=1;
//no more intersect we can go to time p.r and then go to q.l
r.cost+=0;//just need to wait no need to use skill
r.l=p.r;
r.r=q.l;
}
}
}
else if (!p.type){
if (p.l>q.l){
r.cost+=p.l-q.l;
r.l=p.l;//best is back to p.l
r.r=q.r;
r.type=1;
}
else if (p.r<q.l){
r.cost+=0;//just need to wait
r.l=p.r;//best to wait and go in p.r;
r.r=q.r;
r.type=1;
}
else {
r.cost+=0;
r.l=q.l;//change to [q.l,q.l]
r.r=q.r;
r.type=1;
}
}
else if (!q.type){
r.l=p.l;//just length 1
if (p.r<q.l){
r.cost+=0;//just need to wait
r.r=q.l;
r.type=1;
}
else if (p.r>q.r){
r.cost+=p.r-q.r;//use skill to back time
r.r=q.r;
r.type=1;
}
else {//q.l<=p.r<=q.r;
r.r=p.r;
r.cost+=0;
r.type=1;
}
}
else {
r.type=1;
r.l=p.l;
r.r=q.r;
if (p.r>q.l){
r.cost+=p.r-q.l;//backtime
}
else if (p.r<=q.l){
r.cost+=0;//just wait
}
}
return r;
}
struct IT{
vector<node>st;
void resz(int n){
st.resize(4*n+9);
}
void update(int id,int l,int r,int u,int x,int y){
if (l>u||r<u)return;
if (l==r){
st[id].type=0;
st[id].l=x,st[id].r=y;
st[id].cost=0;
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,x,y);
update(id*2+1,mid+1,r,u,x,y);
st[id]=st[id*2]+st[id*2+1];
}
node get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return {0,-inf,inf,0};
if (u<=l&&r<=v)return st[id];
int mid=(l+r)/2;
return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
}
}st1,st2;
int n,q;
void update(int id,int l,int r){
st1.update(1,1,n-1,id,l-id,r-id-1);
id=n-id;
st2.update(1,1,n-1,id,l-id,r-id-1);
}
long long get(int x,int y,int u,int v){
if (x==y)return max(0,u-v);
if (x<y){
y--;
node in={0,u-x,u-x,0};
node tmp=st1.get(1,1,n-1,x,y);
node out={0,v-y-1,v-y-1,0};
//cout<<tmp.l<<" "<<tmp.r<<" "<<tmp.cost<<'\n';
node ans=in+tmp+out;
return ans.cost;
}
else {
y=n-y;
x=n+1-x;
node in={0,u-x,u-x,0};
node tmp=st2.get(1,1,n-1,x,y);
node out={0,v-y-1,v-y-1,0};
node ans=in+tmp+out;
return ans.cost;
}
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>q;
    st1.resz(n-1),st2.resz(n-1);
    for1(i,1,n-1){
    int l,r;
    cin>>l>>r;
    update(i,l,r);
    }
    for1(i,1,q){
    int type;
    cin>>type;
    if (type==1){
    int id,l,r;
    cin>>id>>l>>r;
    update(id,l,r);
    }
    else {
    int x,y,u,v;
    cin>>x>>u>>y>>v;
    cout<<get(x,y,u,v)<<'\n';
    }
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 30 / 30
• Subtask 3: 66 / 66