oj.uz

Submission #383616

# Submission time Handle Problem Language Result Execution time Memory
383616 2021-03-30T11:50:55 Z mehrdad_sohrabi Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 96364 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=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

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 4774 ms 82664 KB Output is correct
2 Correct 4808 ms 82688 KB Output is correct
3 Correct 4844 ms 85432 KB Output is correct
4 Correct 4750 ms 82796 KB Output is correct
5 Correct 4820 ms 82672 KB Output is correct
6 Correct 45 ms 78700 KB Output is correct
7 Correct 46 ms 78700 KB Output is correct
8 Correct 45 ms 78700 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 78700 KB Output is correct
2 Correct 47 ms 78700 KB Output is correct
3 Correct 47 ms 78700 KB Output is correct
4 Correct 46 ms 78700 KB Output is correct
5 Correct 45 ms 78700 KB Output is correct
6 Correct 46 ms 78700 KB Output is correct
7 Correct 46 ms 78700 KB Output is correct
8 Correct 47 ms 78700 KB Output is correct
9 Correct 45 ms 78700 KB Output is correct
10 Correct 47 ms 78828 KB Output is correct
11 Correct 136 ms 81132 KB Output is correct
12 Correct 46 ms 78828 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1696 ms 79084 KB Output is correct
2 Correct 1432 ms 78956 KB Output is correct
3 Correct 1712 ms 78980 KB Output is correct
4 Correct 1689 ms 79084 KB Output is correct
5 Correct 1628 ms 79104 KB Output is correct
6 Correct 47 ms 78700 KB Output is correct
7 Correct 49 ms 78828 KB Output is correct
8 Correct 46 ms 78700 KB Output is correct
9 Correct 7037 ms 79084 KB Output is correct
10 Correct 63 ms 78700 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4758 ms 86656 KB Output is correct
2 Correct 4818 ms 86636 KB Output is correct
3 Correct 4771 ms 86640 KB Output is correct
4 Correct 4900 ms 88188 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1697 ms 79084 KB Output is correct
2 Correct 1450 ms 79084 KB Output is correct
3 Correct 1709 ms 78980 KB Output is correct
4 Correct 1694 ms 78976 KB Output is correct
5 Correct 1645 ms 79084 KB Output is correct
6 Correct 4794 ms 86636 KB Output is correct
7 Correct 4791 ms 86636 KB Output is correct
8 Correct 4839 ms 86640 KB Output is correct
9 Correct 4878 ms 88260 KB Output is correct
10 Correct 4715 ms 82664 KB Output is correct
11 Correct 4673 ms 82796 KB Output is correct
12 Correct 4753 ms 85484 KB Output is correct
13 Correct 4654 ms 82668 KB Output is correct
14 Correct 4671 ms 82796 KB Output is correct
15 Correct 47 ms 78700 KB Output is correct
16 Correct 45 ms 78700 KB Output is correct
17 Correct 45 ms 78700 KB Output is correct
18 Correct 45 ms 78700 KB Output is correct
19 Correct 47 ms 78700 KB Output is correct
20 Correct 46 ms 78700 KB Output is correct
21 Correct 46 ms 78828 KB Output is correct
22 Correct 45 ms 78700 KB Output is correct
23 Correct 45 ms 78700 KB Output is correct
24 Correct 45 ms 78700 KB Output is correct
25 Correct 129 ms 81132 KB Output is correct
26 Correct 45 ms 78700 KB Output is correct
27 Correct 7124 ms 78976 KB Output is correct
28 Execution timed out 20110 ms 90688 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1678 ms 79024 KB Output is correct
2 Correct 1438 ms 78968 KB Output is correct
3 Correct 1716 ms 79084 KB Output is correct
4 Correct 1677 ms 79084 KB Output is correct
5 Correct 1645 ms 78980 KB Output is correct
6 Correct 4891 ms 86748 KB Output is correct
7 Correct 4861 ms 86636 KB Output is correct
8 Correct 4850 ms 86764 KB Output is correct
9 Correct 4903 ms 88440 KB Output is correct
10 Correct 4751 ms 82540 KB Output is correct
11 Correct 4779 ms 82676 KB Output is correct
12 Correct 4878 ms 85484 KB Output is correct
13 Correct 4778 ms 82676 KB Output is correct
14 Correct 4776 ms 82796 KB Output is correct
15 Correct 2904 ms 96364 KB Output is correct
16 Execution timed out 20092 ms 94704 KB Time limit exceeded
17 Halted 0 ms 0 KB -