oj.uz

Submission #252471

# Submission time Handle Problem Language Result Execution time Memory
252471 2020-07-25T16:03:53 Z eohomegrownapps Wall (IOI14_wall) C++14
100 / 100
 2980 ms 204804 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

//segment tree, rmaxq

struct Node{
    int s,e,m,v=0;
    Node *l, *r;
    Node(int _s, int _e){
        s=_s;e=_e;
        if (s==e){
            return;
        }
        m=(s+e)/2;
        l = new Node(s,m);
        r = new Node(m+1,e);
    }
    void update(int ind, int val){
        //cout<<"upd "<<ind<<" "<<val<<'\n';
        if (s==e){
            v=val;
            return;
        }
        if (ind<=m){
            l->update(ind,val);
        } else {
            r->update(ind,val);
        }
        v=max(l->v,r->v);
    }
    int query(int a, int b){
        if (s==a&&e==b){
            return v;
        }
        if (b<=m){
            return l->query(a,b);
        } else if (m<a){
            return r->query(a,b);
        } else {
            return max(l->query(a,m),r->query(m+1,b));
        }
    }
};

Node *radd;
Node *rrem;
int MX = 100001;
int n,k;
bool success(int x){
    if (x==k){return true;}
    return (radd->query(x,k-1)+rrem->query(x,k-1))<=MX;
}

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
    n=N;k=K;
    vector<pair<int,pair<int,bool>>> ptrs[2000000]; 
    int kadd[500000];
    //{time,{height,add/rem}}
    for (int i = 0; i<k; i++){
        bool phase = (op[i]-1);
        int h = height[i];
        int l = left[i];
        int r = right[i];
        if (phase){
            h=MX-h;
        }
        ptrs[l].push_back({i,{h,phase}});
        if (r!=n-1){
            ptrs[r+1].push_back({i,{0,phase}});
        }
        kadd[i]=0;
    }
    radd=new Node(0,k-1);
    rrem=new Node(0,k-1);
    int prevval = 0;
    for (int x = 0; x<n; x++){
        //cout<<x<<":\n";
        //process x
        if (ptrs[x].size()==0){
            finalHeight[x]=prevval;
            //cout<<prevval<<'\n';
            continue;
        }
        for (auto i : ptrs[x]){
            int time = i.first;
            int h = i.second.first;
            int isRem = i.second.second;
            if (isRem){
                rrem->update(time,h);
            } else {
                radd->update(time,h);
                kadd[time]=h;
            }
        }
        int l = 0, r = k-1;
        while (l<=r){
            int mid = (l+r)/2;
            //cout<<mid<<'\n';
            if (success(mid)){
                r=mid-1;
            } else {
                l=mid+1;
            }
        }
        //cout<<"bleh\n";
        if (l==0){
            //there is no overlap
            finalHeight[x] = radd->query(0,k-1);
        } else {
            //there is overlap
            int lastind = l-1;
            int addafter = radd->query(lastind,k-1);
            int remafter = rrem->query(lastind,k-1);
            int addval = kadd[lastind];
            if (addval+remafter>MX){
                //remove is after
                finalHeight[x]=MX-remafter;
            } else {
                //add is after
                finalHeight[x]=addafter;
            }
        }
        prevval=finalHeight[x];
        //cout<<prevval<<'\n';
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47232 KB Output is correct
2 Correct 29 ms 48376 KB Output is correct
3 Correct 32 ms 47736 KB Output is correct
4 Correct 36 ms 48640 KB Output is correct
5 Correct 37 ms 48632 KB Output is correct
6 Correct 36 ms 48632 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47232 KB Output is correct
2 Correct 359 ms 156892 KB Output is correct
3 Correct 425 ms 97532 KB Output is correct
4 Correct 1506 ms 169732 KB Output is correct
5 Correct 646 ms 168288 KB Output is correct
6 Correct 594 ms 168208 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47232 KB Output is correct
2 Correct 29 ms 48384 KB Output is correct
3 Correct 28 ms 47744 KB Output is correct
4 Correct 36 ms 48636 KB Output is correct
5 Correct 37 ms 48632 KB Output is correct
6 Correct 36 ms 48640 KB Output is correct
7 Correct 26 ms 47232 KB Output is correct
8 Correct 354 ms 156928 KB Output is correct
9 Correct 419 ms 97528 KB Output is correct
10 Correct 1472 ms 169736 KB Output is correct
11 Correct 623 ms 168312 KB Output is correct
12 Correct 596 ms 168312 KB Output is correct
13 Correct 27 ms 47232 KB Output is correct
14 Correct 341 ms 156848 KB Output is correct
15 Correct 98 ms 55164 KB Output is correct
16 Correct 1589 ms 170024 KB Output is correct
17 Correct 626 ms 167672 KB Output is correct
18 Correct 633 ms 167416 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47232 KB Output is correct
2 Correct 29 ms 48384 KB Output is correct
3 Correct 28 ms 47744 KB Output is correct
4 Correct 38 ms 48632 KB Output is correct
5 Correct 37 ms 48632 KB Output is correct
6 Correct 37 ms 48632 KB Output is correct
7 Correct 27 ms 47232 KB Output is correct
8 Correct 336 ms 156892 KB Output is correct
9 Correct 433 ms 97528 KB Output is correct
10 Correct 1523 ms 169592 KB Output is correct
11 Correct 637 ms 168276 KB Output is correct
12 Correct 581 ms 168312 KB Output is correct
13 Correct 26 ms 47232 KB Output is correct
14 Correct 336 ms 156888 KB Output is correct
15 Correct 92 ms 55032 KB Output is correct
16 Correct 1719 ms 170100 KB Output is correct
17 Correct 632 ms 167672 KB Output is correct
18 Correct 637 ms 167416 KB Output is correct
19 Correct 2886 ms 194296 KB Output is correct
20 Correct 2927 ms 191992 KB Output is correct
21 Correct 2906 ms 194296 KB Output is correct
22 Correct 2805 ms 202136 KB Output is correct
23 Correct 2819 ms 202252 KB Output is correct
24 Correct 2852 ms 202184 KB Output is correct
25 Correct 2810 ms 202160 KB Output is correct
26 Correct 2962 ms 204804 KB Output is correct
27 Correct 2876 ms 204724 KB Output is correct
28 Correct 2873 ms 202104 KB Output is correct
29 Correct 2980 ms 202164 KB Output is correct
30 Correct 2743 ms 202104 KB Output is correct