제출 #865397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
865397		guagua0407	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	컴파일 에러	0 ms	0 KiB

timeleap

//#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{
    int s1,s2,e1,e2,sz;
    ll c1,c2;
};

const int mxn=3e5+5;
vector<vector<node>> segtree(2,vector<node>(mxn*4));
int n,q;
int L[mxn],R[mxn];
node trash;
int cnt=0;

void merge(node &ans,node &a,node &b){
    if(a.sz==-1){
        ans=b;
        return;
    }
    if(b.sz==-1){
        ans=a;
        return;
    }
    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){
            ll 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){
            ll 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;
        }
    }
}

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);
    if(segtree[id][v*2].sz==-1){
        segtree[id][v]=segtree[id][v*2+1];
        return;
    }
    if(segtree[id][v*2+1].sz==-1){
        segtree[id][v]=segtree[id][v*2];
        return;
    }
    segtree[id][v].sz=segtree[id][v*2].sz+segtree[id][v*2+1].sz;
    segtree[id][v].s1=segtree[id][v*2].s1;
    segtree[id][v].s2=segtree[id][v*2].s2;
    {
        segtree[id][v].c1=segtree[id][v*2].c1;
        if(segtree[id][v*2].e1>segtree[id][v*2+1].s1){
            segtree[id][v].c1+=segtree[id][v*2+1].c1+(segtree[id][v*2].e1-segtree[id][v*2+1].s1);
            segtree[id][v].e1=segtree[id][v*2+1].e1;
        }
        else if(segtree[id][v*2].e1>=segtree[id][v*2+1].s2){
            ll dif=segtree[id][v*2+1].c1-segtree[id][v*2+1].c2;
            segtree[id][v].c1+=segtree[id][v*2+1].c2+max(0ll,dif-(segtree[id][v*2+1].s1-segtree[id][v*2].e1));
            int res=segtree[id][v*2].e1+segtree[id][v*2+1].sz;
            if(res>segtree[id][v*2+1].e1){
                segtree[id][v].e1=segtree[id][v*2+1].e1;
            }
            else{
                segtree[id][v].e1=max(res,segtree[id][v*2+1].e2);
            }
        }
        else{
            segtree[id][v].c1+=segtree[id][v*2+1].c2;
            segtree[id][v].e1=segtree[id][v*2+1].e2;
        }
    }
    {
        segtree[id][v].c2=segtree[id][v*2].c2;
        if(segtree[id][v*2].e2>segtree[id][v*2+1].s1){
            segtree[id][v].c2+=segtree[id][v*2+1].c1+(segtree[id][v*2].e2-segtree[id][v*2+1].s1);
            segtree[id][v].e2=segtree[id][v*2+1].e1;
        }
        else if(segtree[id][v*2].e2>=segtree[id][v*2+1].s2){
            ll dif=segtree[id][v*2+1].c1-segtree[id][v*2+1].c2;
            segtree[id][v].c2+=segtree[id][v*2+1].c2+max(0ll,dif-(segtree[id][v*2+1].s1-segtree[id][v*2].e2));
            int res=segtree[id][v*2].e2+segtree[id][v*2+1].sz;
            if(res>segtree[id][v*2+1].e1){
                segtree[id][v].e2=segtree[id][v*2+1].e1;
            }
            else{
                segtree[id][v].e2=max(res,segtree[id][v*2+1].e2);
            }
        }
        else{
            segtree[id][v].c2+=segtree[id][v*2+1].c2;
            segtree[id][v].e2=segtree[id][v*2+1].e2;
        }
    }
}

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);
        if(segtree[id][v*2].sz==-1){
        segtree[id][v]=segtree[id][v*2+1];
        return;
    }
    if(segtree[id][v*2+1].sz==-1){
        segtree[id][v]=segtree[id][v*2];
        return;
    }
    segtree[id][v].sz=segtree[id][v*2].sz+segtree[id][v*2+1].sz;
    segtree[id][v].s1=segtree[id][v*2].s1;
    segtree[id][v].s2=segtree[id][v*2].s2;
    {
        segtree[id][v].c1=segtree[id][v*2].c1;
        if(segtree[id][v*2].e1>segtree[id][v*2+1].s1){
            segtree[id][v].c1+=segtree[id][v*2+1].c1+(segtree[id][v*2].e1-segtree[id][v*2+1].s1);
            segtree[id][v].e1=segtree[id][v*2+1].e1;
        }
        else if(segtree[id][v*2].e1>=segtree[id][v*2+1].s2){
            ll dif=segtree[id][v*2+1].c1-segtree[id][v*2+1].c2;
            segtree[id][v].c1+=segtree[id][v*2+1].c2+max(0ll,dif-(segtree[id][v*2+1].s1-segtree[id][v*2].e1));
            int res=segtree[id][v*2].e1+segtree[id][v*2+1].sz;
            if(res>segtree[id][v*2+1].e1){
                segtree[id][v].e1=segtree[id][v*2+1].e1;
            }
            else{
                segtree[id][v].e1=max(res,segtree[id][v*2+1].e2);
            }
        }
        else{
            segtree[id][v].c1+=segtree[id][v*2+1].c2;
            segtree[id][v].e1=segtree[id][v*2+1].e2;
        }
    }
    {
        segtree[id][v].c2=segtree[id][v*2].c2;
        if(segtree[id][v*2].e2>segtree[id][v*2+1].s1){
            segtree[id][v].c2+=segtree[id][v*2+1].c1+(segtree[id][v*2].e2-segtree[id][v*2+1].s1);
            segtree[id][v].e2=segtree[id][v*2+1].e1;
        }
        else if(segtree[id][v*2].e2>=segtree[id][v*2+1].s2){
            ll dif=segtree[id][v*2+1].c1-segtree[id][v*2+1].c2;
            segtree[id][v].c2+=segtree[id][v*2+1].c2+max(0ll,dif-(segtree[id][v*2+1].s1-segtree[id][v*2].e2));
            int res=segtree[id][v*2].e2+segtree[id][v*2+1].sz;
            if(res>segtree[id][v*2+1].e1){
                segtree[id][v].e2=segtree[id][v*2+1].e1;
            }
            else{
                segtree[id][v].e2=max(res,segtree[id][v*2+1].e2);
            }
        }
        else{
            segtree[id][v].c2+=segtree[id][v*2+1].c2;
            segtree[id][v].e2=segtree[id][v*2+1].e2;
        }
    }

}

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;
    if(!(mid<tl or min(mid,tr)<l)) return query(id,max(mid+1,tl),tr,mid+1,r,v*2+1);
    if(!(r<min(tl,mid+1) or tr<mid+1)) return node a=query(id,tl,min(mid,tr),l,mid,v*2);
    node a=query(id,tl,min(mid,tr),l,mid,v*2);
    node b=query(id,max(mid+1,tl),tr,mid+1,r,v*2+1);
    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){
            ll 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){
            ll 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;
}

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{
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            if(a==c){
                cout<<max(0,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));
                int 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(0,fin-d)<<'\n';;
        }
    }
    return 0;
}
//maybe its multiset not set

컴파일 시 표준 에러 (stderr) 메시지

timeleap.cpp: In function 'node query(int, int, int, int, int, int)':
timeleap.cpp:234:52: error: expected primary-expression before 'a'
  234 |     if(!(r<min(tl,mid+1) or tr<mid+1)) return node a=query(id,tl,min(mid,tr),l,mid,v*2);
      |                                                    ^
timeleap.cpp:234:51: error: expected ';' before 'a'
  234 |     if(!(r<min(tl,mid+1) or tr<mid+1)) return node a=query(id,tl,min(mid,tr),l,mid,v*2);
      |                                                   ^~
      |                                                   ;
timeleap.cpp:234:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  234 |     if(!(r<min(tl,mid+1) or tr<mid+1)) return node a=query(id,tl,min(mid,tr),l,mid,v*2);
      |     ^~
timeleap.cpp:234:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  234 |     if(!(r<min(tl,mid+1) or tr<mid+1)) return node a=query(id,tl,min(mid,tr),l,mid,v*2);
      |                                                    ^
timeleap.cpp:234:52: error: 'a' was not declared in this scope
timeleap.cpp: In function 'void setIO(std::string)':
timeleap.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~