oj.uz

Submission #383636

# Submission time Handle Problem Language Result Execution time Memory
383636 2021-03-30T12:45:52 Z mehrdad_sohrabi Wombats (IOI13_wombats) C++14
27 / 100
 1262 ms 22164 KB 
#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=100;
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++;
    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;
}
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;
            //}
            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
*/

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12140 KB Output is correct
2 Correct 41 ms 12140 KB Output is correct
3 Correct 123 ms 13804 KB Output is correct
4 Correct 40 ms 12140 KB Output is correct
5 Correct 40 ms 12268 KB Output is correct
6 Correct 7 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct
8 Correct 7 ms 8172 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 7 ms 8172 KB Output is correct
4 Incorrect 9 ms 8556 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1209 ms 21868 KB Output is correct
2 Correct 890 ms 18796 KB Output is correct
3 Incorrect 1246 ms 22124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 16888 KB Output is correct
2 Correct 375 ms 17004 KB Output is correct
3 Correct 306 ms 17004 KB Output is correct
4 Correct 347 ms 17772 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1204 ms 21984 KB Output is correct
2 Correct 855 ms 18540 KB Output is correct
3 Incorrect 1233 ms 22124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1262 ms 21868 KB Output is correct
2 Correct 871 ms 18668 KB Output is correct
3 Incorrect 1219 ms 22164 KB Output isn't correct
4 Halted 0 ms 0 KB -