Submission #944230

#	Time	Username	Problem	Language	Result	Execution time	Memory
944230		yeediot	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	624 ms	92076 KiB

timeleap

#include<bits/stdc++.h>
#include <ostream>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct line{
    int a,b;
    int operator()(const int x)const{
        return a*x+b;
    }
};
bool check(line l1,line l2,line l3){
    return (l3.b-l2.b)*(l1.a-l2.a)<=(l2.b-l1.b)*(l2.a-l3.a);
}
struct node{
    int ty,l,r,k;
    node(int ty=0,int l=0,int r=0,int k=0):ty(ty),l(l),r(r),k(k){}
};
const int mxn=3e5+5;
node seg[2][4*mxn];
node merge(node a,node b){
    //ty=0 代表該道路可在l~r之間使用，ty=1代表該區間起點在l,終點在r。
    node res=node();
    if(a.ty==0 and b.ty==0){
        if(max(a.l,b.l)<=min(a.r,b.r)){
            res=node(0,max(a.l,b.l),min(a.r,b.r),0);
        }
        else if(a.r<b.r){
            res=node(1,a.r,b.l,0);
        }
        else{
            res=node(1,a.l,b.r,max(0LL,a.l-b.r));
        }
    }
    else if(a.ty==0){
        res=node(1,max(a.l,min(a.r,b.l)),b.r,max(0LL,a.l-b.l));
    }
    else if(b.ty==0){
        res=node(1,a.l,max(b.l,min(a.r,b.r)),max(a.r-b.r,0LL));
    }
    else{
        res=node(1,a.l,b.r,max(0LL,a.r-b.l));
    }
    res.k+=a.k+b.k;
    return res;
}
void modify(bool f,int l,int r,int id,int p,node v){
    if(l==r){
        seg[f][id]=v;
        return ;
    }
    int mm=l+r>>1;
    if(p<=mm){
        modify(f,l,mm,id*2,p,v);
    }
    else{
        modify(f,mm+1,r,id*2+1,p,v);
    }
    if(!f)seg[f][id]=merge(seg[f][id*2],seg[f][id*2+1]);
    else seg[f][id]=merge(seg[f][id*2+1],seg[f][id*2]);
}
node query(bool f,int l,int r,int id,int ql,int qr){
    if(ql<=l and r<=qr){
        return seg[f][id];
    }
    int mm=l+r>>1;
    if(qr<=mm){
        return query(f,l,mm,id*2,ql,qr);
    }
    else if(ql>mm){
        return query(f,mm+1,r,id*2+1,ql,qr);
    }
    else{
        if(!f)return merge(query(f,l,mm,id*2,ql,mm),query(f,mm+1,r,id*2+1,mm+1,qr));
        else return merge(query(f,mm+1,r,id*2+1,mm+1,qr),query(f,l,mm,id*2,ql,mm));
    }
}
void operator<<(ostream&os,node a){
    cout<<a.ty<<','<<a.l<<','<<a.r<<','<<a.k<<' ';
}
signed main(){
    setio();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<n;i++){
        int l,r;
        cin>>l>>r;
        r--;
        node x=node(0,l-i,r-i,0);
        modify(0,1,n-1,1,i,x);
        x=node(0,l+i+1,r+i+1,0);
        modify(1,1,n-1,1,i,x);
    }
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int p,l,r;
            cin>>p>>l>>r;
            r--;
            node x=node(0,l-p,r-p,0);
            modify(0,1,n-1,1,p,x);
            x=node(0,l+p+1,r+p+1,0);
            modify(1,1,n-1,1,p,x);
        }
        else{
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            if(a==c){
                cout<<max(b-d,0LL)<<'\n';
                continue;
            }
            if(a<c){
                b-=a;
                d-=c;
                cout<<merge(merge(node(0,b,b,0),query(0,1,n-1,1,a,c-1)),node(0,d,d,0)).k<<'\n';
            }
            else{
                b+=a;
                d+=c;
                cout<<merge(merge(node(0,b,b,0),query(1,1,n-1,1,c,a-1)),node(0,d,d,0)).k<<'\n';
                //a--;
                //b+=a;
                //d+=c-1;
            }
        }
    }
}
 /*
 input:
 [  {  ]  }
 {  [  }  ]
 [  ]  {  }
 {  }  [  ]
 [  {  }  ]
 {  [  ]  }
 */















 

Compilation message (stderr)

timeleap.cpp: In function 'void modify(bool, long long int, long long int, long long int, long long int, node)':
timeleap.cpp:92:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mm=l+r>>1;
      |            ~^~
timeleap.cpp: In function 'node query(bool, long long int, long long int, long long int, long long int, long long int)':
timeleap.cpp:106:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int mm=l+r>>1;
      |            ~^~
timeleap.cpp: In function 'void setIO(std::string)':
timeleap.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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