oj.uz

Submission #252467

# Submission time Handle Problem Language Result Execution time Memory
252467 2020-07-25T16:00:52 Z eohomegrownapps Wall (IOI14_wall) C++14
61 / 100
 3000 ms 192564 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<vector<pair<int,pair<int,bool>>>> ptrs(n); 
    //{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}});
        }
    }
    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);
            }
        }
        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 = radd->query(lastind,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 1 ms 256 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 12 ms 1792 KB Output is correct
5 Correct 12 ms 1792 KB Output is correct
6 Correct 13 ms 1792 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 319 ms 107996 KB Output is correct
3 Correct 419 ms 50168 KB Output is correct
4 Correct 1482 ms 123096 KB Output is correct
5 Correct 611 ms 120948 KB Output is correct
6 Correct 583 ms 121080 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 3 ms 1408 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 13 ms 1792 KB Output is correct
5 Correct 13 ms 1792 KB Output is correct
6 Correct 12 ms 1792 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 323 ms 113756 KB Output is correct
9 Correct 413 ms 53880 KB Output is correct
10 Correct 1504 ms 132824 KB Output is correct
11 Correct 609 ms 131328 KB Output is correct
12 Correct 569 ms 129584 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 329 ms 113988 KB Output is correct
15 Correct 66 ms 8824 KB Output is correct
16 Correct 1615 ms 132524 KB Output is correct
17 Correct 646 ms 129912 KB Output is correct
18 Correct 618 ms 129528 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 13 ms 1920 KB Output is correct
5 Correct 13 ms 1792 KB Output is correct
6 Correct 12 ms 1792 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 351 ms 113884 KB Output is correct
9 Correct 403 ms 53880 KB Output is correct
10 Correct 1456 ms 132600 KB Output is correct
11 Correct 622 ms 131192 KB Output is correct
12 Correct 580 ms 129532 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 331 ms 113756 KB Output is correct
15 Correct 66 ms 8952 KB Output is correct
16 Correct 1892 ms 132516 KB Output is correct
17 Correct 620 ms 129656 KB Output is correct
18 Correct 667 ms 129400 KB Output is correct
19 Execution timed out 3037 ms 192564 KB Time limit exceeded
20 Halted 0 ms 0 KB -