Submission #383616

#TimeUsernameProblemLanguageResultExecution timeMemory
383616mehrdad_sohrabiWombats (IOI13_wombats)C++14
55 / 100
20110 ms96364 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=60; ll L[N*M],R[N*M],seg[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++; L[NOD]=L[nod]; R[NOD]=R[nod]; seg[NOD]=seg[nod]; if (l>=le && r<=re){ seg[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); return NOD; } void shift(ll nod){ seg[ts]=seg[L[nod]]; L[ts]=L[L[nod]]; R[ts]=R[L[nod]]; L[nod]=ts; seg[ts]+=seg[nod]; ts++; seg[ts]=seg[R[nod]]; L[ts]=L[R[nod]]; R[ts]=R[R[nod]]; R[nod]=ts; seg[ts]+=seg[nod]; ts++; seg[nod]=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]; 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); } 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; } int n,m; int h[5000][200],v[5000][200]; void solve(int RR, int C) { /* ... */ ts=1; for (int i=0;i<N*M;i++) L[i]=0,R[i]=0,seg[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; // cout << "GOOZ" << 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; } // cout << get(root[1],0,m,3) << endl; 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; } 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]; } intit(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 */

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;
      |      ^~~
#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...