oj.uz

Submission #383808

# Submission time Handle Problem Language Result Execution time Memory
383808 2021-03-30T20:19:41 Z mehrdad_sohrabi Wombats (IOI13_wombats) C++14
27 / 100
 1259 ms 25712 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=500;
ll L[N*M],R[N*M],seg[N*M],mx[N*M];
ll ts=1;
ll root[210];

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;
}
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)) {
        ll z=1;
        for (int i=0;i<(long long)1e12;i++){
            z*=i;
        }
    }
}
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)) {
        ll z=1;
        for (int i=0;i<(long long)1e12;i++){
            z*=i;
        }
    }
    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;
    shift(NOD);
    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];
    if (mx[NOD]!=get(NOD,l,r,l)) cout << 1/0;
    return NOD;
}
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];
    if (mx[nod1]!=get(nod1,l,r,l)) cout << 1/0;
}
vector <int> node;
void bfs(ll nod,ll l,ll r){
    node.pb(nod);
}
ll getmn(ll nod1,ll nod2,ll l,ll r,ll b,ll A,ll B){
    if (r-l==1){
        if (mx[nod1]+b>mx[nod2]) return -1;
        return l;
    }
    ll mid=(r+l)/2;
    shift(nod1);
    shift(nod2);
    if (mx[R[nod1]]+b<=mx[R[nod2]]) return getmn(R[nod1],R[nod2],mid,r,b,A+seg[nod1],B+seg[nod2]);
    else return getmn(L[nod1],L[nod2],l,mid,b,A+seg[nod1],B+seg[nod2]);
}
int n,m;
int h[5000][200],v[5000][200];

void solve(int RR, int C) {
    /* ... */
    for (int i=0;i<ts;i++) L[i]=0,R[i]=0,seg[i]=0,mx[i]=0;
    ts=1;
    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)1e5);
        }
    }
   // 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],0,0);
         //   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],0,0);
            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

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:80:43: warning: division by zero [-Wdiv-by-zero]
   80 |     if (mx[NOD]!=get(NOD,l,r,l)) cout << 1/0;
      |                                          ~^~
wombats.cpp: In function 'void cop(ll, ll, ll, ll, ll, ll)':
wombats.cpp:98:45: warning: division by zero [-Wdiv-by-zero]
   98 |     if (mx[nod1]!=get(nod1,l,r,l)) cout << 1/0;
      |                                            ~^~
wombats.cpp: In function 'void solve(int, int)':
wombats.cpp:136:21: warning: unused variable 'r' [-Wunused-variable]
  136 |             ll l=-1,r=m;
      |                     ^
wombats.cpp:161:16: warning: unused variable 'l' [-Wunused-variable]
  161 |             ll l=-1,r=m;
      |                ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12140 KB Output is correct
2 Correct 40 ms 12140 KB Output is correct
3 Correct 126 ms 13856 KB Output is correct
4 Correct 40 ms 12140 KB Output is correct
5 Correct 40 ms 12140 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 6 ms 8192 KB Output is correct
8 Correct 6 ms 8172 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1231 ms 25452 KB Output is correct
2 Correct 763 ms 20844 KB Output is correct
3 Incorrect 1236 ms 25712 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 281 ms 16876 KB Output is correct
2 Correct 299 ms 17004 KB Output is correct
3 Correct 279 ms 16876 KB Output is correct
4 Correct 328 ms 17772 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1213 ms 25324 KB Output is correct
2 Correct 785 ms 20716 KB Output is correct
3 Incorrect 1243 ms 25524 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1219 ms 25452 KB Output is correct
2 Correct 750 ms 20716 KB Output is correct
3 Incorrect 1259 ms 25708 KB Output isn't correct
4 Halted 0 ms 0 KB -