Submission #944230

#TimeUsernameProblemLanguageResultExecution timeMemory
944230yeediotBitaro, who Leaps through Time (JOI19_timeleap)C++17
100 / 100
624 ms92076 KiB
#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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...