oj.uz

Submission #383773

# Submission time Handle Problem Language Result Execution time Memory
383773 2021-03-30T19:38:38 Z mehrdad_sohrabi Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 262144 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];
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;
    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)) {
        ll z=1;
        for (int i=0;i<(long long)1e12;i++){
            z*=i;
        }
    }
}
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,ll A,ll B){
    if (r-l==1){
        if (mx[nod1]+A+b>mx[nod2]+B) 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) {
    /* ... */
    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],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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12172 KB Output is correct
2 Correct 44 ms 12140 KB Output is correct
3 Correct 122 ms 13804 KB Output is correct
4 Correct 45 ms 12268 KB Output is correct
5 Correct 44 ms 12140 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 7 ms 8172 KB Output is correct
8 Correct 7 ms 8172 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8172 KB Output is correct
2 Correct 7 ms 8172 KB Output is correct
3 Correct 7 ms 8172 KB Output is correct
4 Correct 7 ms 8428 KB Output is correct
5 Correct 7 ms 8428 KB Output is correct
6 Correct 7 ms 8428 KB Output is correct
7 Correct 7 ms 8428 KB Output is correct
8 Correct 7 ms 8428 KB Output is correct
9 Correct 7 ms 8428 KB Output is correct
10 Correct 7 ms 8428 KB Output is correct
11 Correct 90 ms 9508 KB Output is correct
12 Correct 7 ms 8428 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1138 ms 17900 KB Output is correct
2 Correct 729 ms 14316 KB Output is correct
3 Correct 1170 ms 18284 KB Output is correct
4 Correct 1103 ms 18028 KB Output is correct
5 Correct 1051 ms 17516 KB Output is correct
6 Correct 7 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct
8 Correct 6 ms 8172 KB Output is correct
9 Correct 3605 ms 14624 KB Output is correct
10 Correct 7 ms 8172 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 16620 KB Output is correct
2 Correct 255 ms 16620 KB Output is correct
3 Correct 239 ms 16492 KB Output is correct
4 Correct 286 ms 17388 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 18028 KB Output is correct
2 Correct 733 ms 14424 KB Output is correct
3 Correct 1152 ms 18156 KB Output is correct
4 Correct 1104 ms 18160 KB Output is correct
5 Correct 1068 ms 17516 KB Output is correct
6 Correct 242 ms 16492 KB Output is correct
7 Correct 253 ms 16620 KB Output is correct
8 Correct 240 ms 16620 KB Output is correct
9 Correct 287 ms 17516 KB Output is correct
10 Correct 43 ms 12140 KB Output is correct
11 Correct 44 ms 12140 KB Output is correct
12 Correct 123 ms 13804 KB Output is correct
13 Correct 45 ms 12140 KB Output is correct
14 Correct 44 ms 12140 KB Output is correct
15 Correct 6 ms 8172 KB Output is correct
16 Correct 6 ms 8172 KB Output is correct
17 Correct 6 ms 8172 KB Output is correct
18 Correct 7 ms 8428 KB Output is correct
19 Correct 7 ms 8428 KB Output is correct
20 Correct 7 ms 8428 KB Output is correct
21 Correct 7 ms 8428 KB Output is correct
22 Correct 7 ms 8428 KB Output is correct
23 Correct 7 ms 8428 KB Output is correct
24 Correct 7 ms 8428 KB Output is correct
25 Correct 91 ms 9452 KB Output is correct
26 Correct 7 ms 8428 KB Output is correct
27 Correct 3616 ms 14624 KB Output is correct
28 Execution timed out 20113 ms 238868 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1082 ms 18052 KB Output is correct
2 Correct 735 ms 14444 KB Output is correct
3 Correct 1129 ms 18156 KB Output is correct
4 Correct 1111 ms 18028 KB Output is correct
5 Correct 1058 ms 17516 KB Output is correct
6 Correct 268 ms 16768 KB Output is correct
7 Correct 251 ms 16748 KB Output is correct
8 Correct 248 ms 16620 KB Output is correct
9 Correct 284 ms 17388 KB Output is correct
10 Correct 43 ms 12140 KB Output is correct
11 Correct 47 ms 12140 KB Output is correct
12 Correct 121 ms 13804 KB Output is correct
13 Correct 43 ms 12268 KB Output is correct
14 Correct 45 ms 12140 KB Output is correct
15 Runtime error 702 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -