oj.uz

답안 #383817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
383817 2021-03-30T20:33:04 Z mehrdad_sohrabi 웜뱃 (IOI13_wombats) C++14
55 / 100
 20000 ms 262148 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 (seg[nod1]+b>seg[nod2]) return -1;
        return l;
    }
    ll mid=(r+l)/2;
    shift(nod1);
    shift(nod2);
    if (get(R[nod1],mid,r,mid)!=mx[R[nod1]]) cout << 1/0;
    if (get(R[nod2],mid,r,mid)!=mx[R[nod2]]) cout << 1/0;

    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!=m-1 ){
                ll xx=get(root[i-1],0,m,l+1);
                ll yy=get(root[i],0,m,l+1);
            //    if (xx<yy) cout << 1/0;
            }
            if (l!=-1){
                  ll xx=get(root[i-1],0,m,l);
                ll yy=get(root[i],0,m,l);
           //     if (xx>yy) cout << 1/0;
                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 'll getmn(ll, ll, ll, ll, ll, ll, ll)':
wombats.cpp:112:55: warning: division by zero [-Wdiv-by-zero]
  112 |     if (get(R[nod1],mid,r,mid)!=mx[R[nod1]]) cout << 1/0;
      |                                                      ~^~
wombats.cpp:113:55: warning: division by zero [-Wdiv-by-zero]
  113 |     if (get(R[nod2],mid,r,mid)!=mx[R[nod2]]) cout << 1/0;
      |                                                      ~^~
wombats.cpp: In function 'void solve(int, int)':
wombats.cpp:156:20: warning: unused variable 'xx' [-Wunused-variable]
  156 |                 ll xx=get(root[i-1],0,m,l+1);
      |                    ^~
wombats.cpp:157:20: warning: unused variable 'yy' [-Wunused-variable]
  157 |                 ll yy=get(root[i],0,m,l+1);
      |                    ^~
wombats.cpp:161:22: warning: unused variable 'xx' [-Wunused-variable]
  161 |                   ll xx=get(root[i-1],0,m,l);
      |                      ^~
wombats.cpp:162:20: warning: unused variable 'yy' [-Wunused-variable]
  162 |                 ll yy=get(root[i],0,m,l);
      |                    ^~
wombats.cpp:172:16: warning: unused variable 'l' [-Wunused-variable]
  172 |             ll l=-1,r=m;
      |                ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 12140 KB Output is correct
2 Correct 44 ms 12252 KB Output is correct
3 Correct 121 ms 13804 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 8172 KB Output is correct
8 Correct 6 ms 8172 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8300 KB Output is correct
4 Correct 7 ms 8556 KB Output is correct
5 Correct 7 ms 8428 KB Output is correct
6 Correct 7 ms 8428 KB Output is correct
7 Correct 8 ms 8428 KB Output is correct
8 Correct 8 ms 8704 KB Output is correct
9 Correct 8 ms 8556 KB Output is correct
10 Correct 8 ms 8556 KB Output is correct
11 Correct 99 ms 9708 KB Output is correct
12 Correct 7 ms 8428 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1370 ms 21484 KB Output is correct
2 Correct 794 ms 16492 KB Output is correct
3 Correct 1390 ms 21868 KB Output is correct
4 Correct 1384 ms 21708 KB Output is correct
5 Correct 1269 ms 20844 KB Output is correct
6 Correct 6 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 4003 ms 16932 KB Output is correct
10 Correct 6 ms 8172 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 16620 KB Output is correct
2 Correct 258 ms 16632 KB Output is correct
3 Correct 218 ms 16492 KB Output is correct
4 Correct 268 ms 17372 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1328 ms 21612 KB Output is correct
2 Correct 782 ms 16492 KB Output is correct
3 Correct 1422 ms 21740 KB Output is correct
4 Correct 1335 ms 21612 KB Output is correct
5 Correct 1287 ms 20844 KB Output is correct
6 Correct 218 ms 16620 KB Output is correct
7 Correct 226 ms 16748 KB Output is correct
8 Correct 219 ms 16620 KB Output is correct
9 Correct 258 ms 17388 KB Output is correct
10 Correct 40 ms 12140 KB Output is correct
11 Correct 41 ms 12288 KB Output is correct
12 Correct 121 ms 13804 KB Output is correct
13 Correct 40 ms 12140 KB Output is correct
14 Correct 40 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 8556 KB Output is correct
19 Correct 8 ms 8428 KB Output is correct
20 Correct 9 ms 8428 KB Output is correct
21 Correct 7 ms 8428 KB Output is correct
22 Correct 8 ms 8572 KB Output is correct
23 Correct 7 ms 8556 KB Output is correct
24 Correct 7 ms 8556 KB Output is correct
25 Correct 94 ms 9736 KB Output is correct
26 Correct 7 ms 8428 KB Output is correct
27 Correct 3928 ms 16932 KB Output is correct
28 Execution timed out 20029 ms 241724 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1308 ms 21356 KB Output is correct
2 Correct 786 ms 16620 KB Output is correct
3 Correct 1377 ms 21740 KB Output is correct
4 Correct 1350 ms 21740 KB Output is correct
5 Correct 1268 ms 20992 KB Output is correct
6 Correct 217 ms 16620 KB Output is correct
7 Correct 227 ms 16748 KB Output is correct
8 Correct 218 ms 16492 KB Output is correct
9 Correct 267 ms 17516 KB Output is correct
10 Correct 42 ms 12140 KB Output is correct
11 Correct 40 ms 12244 KB Output is correct
12 Correct 119 ms 13804 KB Output is correct
13 Correct 40 ms 12140 KB Output is correct
14 Correct 46 ms 12268 KB Output is correct
15 Runtime error 612 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -