Submission #383647

#TimeUsernameProblemLanguageResultExecution timeMemory
383647mehrdad_sohrabiWombats (IOI13_wombats)C++14
55 / 100
4255 ms262148 KiB
#include <bits/stdc++.h> #include "wombats.h" /// 500 485 462 A4 using namespace std; typedef int ll; typedef complex<double> point; typedef long double ld; #define pb push_back #define pii pair < ll , ll > #define F first #define S second //#define endl '\n' //#define int long long #define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #define kill(x) return cout<<x<<'\n', 0; const int N=1e5+100,M=500; ll L[N*M],R[N*M],seg[N*M],mx[N*M]; ll ts=1; ll root[210]; int add(ll nod,ll l,ll r,ll le,ll re,ll val){ // cout << nod << " " << l << " " << r << " " << le << endl; if (l>=re || le>=r) return nod; ll NOD=ts; ts++; if (ts>N*(M-1)) cout << 1/0; L[NOD]=L[nod]; R[NOD]=R[nod]; seg[NOD]=seg[nod]; mx[NOD]=mx[nod]; if (l>=le && r<=re){ seg[NOD]+=val; mx[NOD]+=val; return NOD; } ll mid=(r+l)/2; L[NOD]=add(L[NOD],l,mid,le,re,val); R[NOD]=add(R[NOD],mid,r,le,re,val); mx[NOD]=mx[L[NOD]]+seg[NOD]; return NOD; } void shift(ll nod){ seg[ts]=seg[L[nod]]; mx[ts]=mx[L[nod]]; L[ts]=L[L[nod]]; R[ts]=R[L[nod]]; L[nod]=ts; seg[ts]+=seg[nod]; mx[ts]+=seg[nod]; ts++; seg[ts]=seg[R[nod]]; mx[ts]=mx[R[nod]]; L[ts]=L[R[nod]]; R[ts]=R[R[nod]]; R[nod]=ts; seg[ts]+=seg[nod]; mx[ts]+=seg[nod]; ts++; seg[nod]=0; if (ts>N*(M-1)) cout << 1/0; } void cop(ll nod1,ll nod2,ll l,ll r,ll le,ll re){ if (l>=re || le>=r) return ; if (l>=le && r<=re){ L[nod1]=L[nod2]; R[nod1]=R[nod2]; seg[nod1]=seg[nod2]; mx[nod1]=mx[nod2]; return ; } shift(nod1); shift(nod2); ll mid=(r+l)/2; cop(L[nod1],L[nod2],l,mid,le,re); cop(R[nod1],R[nod2],mid,r,le,re); mx[nod1]=mx[L[nod1]]+seg[nod1]; } ll get(ll nod,ll l,ll r,ll id){ if (r-l==1) return seg[nod]; ll mid=(r+l)/2; ll ans=seg[nod]; if (mid>id) ans+=get(L[nod],l,mid,id); else ans+=get(R[nod],mid,r,id); return ans; } ll getmx(ll nod,ll l,ll r,ll id){ if (r-l==1) return mx[nod]; ll mid=(r+l)/2; ll ans=seg[nod]; if (mid>id) ans+=getmx(L[nod],l,mid,id); else ans+=getmx(R[nod],mid,r,id); return ans; } ll getmn(ll nod1,ll nod2,ll l,ll r,ll b){ if (r-l==1){ if (mx[nod1]+b>mx[nod2]) return -1; return l; } shift(nod1); shift(nod2); ll mid=(r+l)/2; if (mx[R[nod1]]+b<=mx[R[nod2]]) return getmn(R[nod1],R[nod2],mid,r,b); else return getmn(L[nod1],L[nod2],l,mid,b); } int n,m; int h[5000][200],v[5000][200]; void solve(int RR, int C) { /* ... */ ts=1; for (int i=0;i<ts;i++) L[i]=0,R[i]=0,seg[i]=0,mx[i]=0; for (int i=0;i<m;i++){ root[i]=ts; ts++; } for (int i=0;i<m;i++){ for (int j=0;j<m;j++){ // cout << j << endl; if (j!=i) root[i]=add(root[i],0,m,j,j+1,(ll)1e9); } } shift(root[1]); // cout << get(root[1],0,m,0) << endl; for (int ii=0;ii<RR;ii++){ /// az samt chap update shavad for (int i=1;i<m;i++){ ll l=-1,r=m; while(r-l>1){ ll mid=(r+l)/2; ll x=get(root[i-1],0,m,mid); ll y=get(root[i],0,m,mid); if (x+h[ii][i-1]<y) l=mid; else r=mid; } ll z=getmn(root[i-1],root[i],0,m,h[ii][i-1]); // if (z!=l){ // cout << ii << " ighjwruthg bad " << i << " " << z << " " << l << endl; // } // cout << get(root[1],0,m,3) << endl; // l=z; if (l!=-1){ cop(root[i],root[i-1],0,m,0,l+1); // cout << get(root[1],0,m,3) << " f " << l+1 << endl; root[i]=add(root[i],0,m,0,l+1,h[ii][i-1]); // if (i==2) cout << "ROO " << get(root[2],0,m,2) << " " << l << endl; } // if (get(root[2],0,m,2)>0) cout << i << " sh " << endl; } for (int i=m-2;i>-1;i--){ ll l=-1,r=m; while(r-l>1){ ll mid=(r+l)/2; ll x=get(root[i+1],0,m,mid); ll y=get(root[i],0,m,mid); if (x+h[ii][i]<y){ r=mid; } else l=mid; } ll z=getmn(root[i],root[i+1],0,m,-h[ii][i]); z++; // if (z!=r){ // cout << "BAD" << " " << ii << " " << i << " " << z << " " << r << endl; // cout << getmx(root[i],0,m,z) << " " << getmx(root[i+1],0,m,z)+h[ii][i] << endl; //} r=z; if (r!=m){ cop(root[i],root[i+1],0,m,r,m); root[i]=add(root[i],0,m,r,m,h[ii][i]); } } // for (int i=0;i<m;i++){ // cout << get(root[1],0,m,i) << " "; // } // cout << endl; if (ii!=RR-1){ for (int i=0;i<m;i++){ // if (i==1) cout << v[ii][i] << endl; root[i]=add(root[i],0,m,0,m,v[ii][i]); // cout << v[ii][i] << endl; // if (i==2) cout << v[ii][i] << " fjn " << get(root[i],0,m,2) << endl; } } } } void init(int R, int C, int H[5000][200], int V[5000][200]){ n=R; m=C; for (int i=0;i<5000;i++) for (int j=0;j<200;j++) h[i][j]=H[i][j],v[i][j]=V[i][j]; solve(n,m); return ; } void changeH(int P, int Q, int W) { /* ... */ h[P][Q]=W; solve(n,m); // cout << "SHASH" << endl; } void changeV(int P, int Q, int W) { /* ... */ v[P][Q]=W; solve(n,m); } int escape(int V1, int V2) { ll ans=get(root[V2],0,m,V1); return ans; } int H[5000][200],V[5000][200]; /* int32_t main(){ cin >> n >> m; for (int i=0;i<n;i++){ for (int j=0;j<m-1;j++) cin >> H[i][j]; } for (int i=0;i<n-1;i++){ for (int j=0;j<m;j++) cin >> V[i][j]; } init(n,m,H,V); ll q; cin >> q; while(q--){ ll ty; cin >> ty; if (ty==3){ ll x,y; cin >> x >> y; cout << escape(x,y) << " ans " << endl; } if (ty==2){ ll x,y,w; cin >> x >> y >> w; changeV(x,y,w); } if (ty==1){ ll x,y,w; cin >> x >> y >> w; changeH(x,y,w); } } } 3 4 0 2 5 7 1 1 0 4 0 0 0 0 2 0 3 4 7 5 3 2 1 3 3 3 2 0 0 5 1 1 1 6 3 2 1 */ //09029292024

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'int add(ll, ll, ll, ll, ll, ll)':
wombats.cpp:26:30: warning: division by zero [-Wdiv-by-zero]
   26 |     if (ts>N*(M-1)) cout << 1/0;
      |                             ~^~
wombats.cpp: In function 'void shift(ll)':
wombats.cpp:60:30: warning: division by zero [-Wdiv-by-zero]
   60 |     if (ts>N*(M-1)) cout << 1/0;
      |                             ~^~
wombats.cpp: In function 'void solve(int, int)':
wombats.cpp:136:16: warning: unused variable 'z' [-Wunused-variable]
  136 |             ll z=getmn(root[i-1],root[i],0,m,h[ii][i-1]);
      |                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...