oj.uz

Submission #252470

# Submission time Handle Problem Language Result Execution time Memory
252470 2020-07-25T16:02:34 Z eohomegrownapps Wall (IOI14_wall) C++14
61 / 100
 3000 ms 194684 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); 
    vector<int> kadd(k,0);
    //{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);
                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 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 18 ms 1920 KB Output is correct
5 Correct 16 ms 1920 KB Output is correct
6 Correct 17 ms 1920 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 346 ms 110172 KB Output is correct
3 Correct 472 ms 51092 KB Output is correct
4 Correct 1877 ms 124988 KB Output is correct
5 Correct 608 ms 123000 KB Output is correct
6 Correct 599 ms 123188 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 11 ms 1920 KB Output is correct
6 Correct 18 ms 1920 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 336 ms 110300 KB Output is correct
9 Correct 449 ms 51192 KB Output is correct
10 Correct 1488 ms 125236 KB Output is correct
11 Correct 625 ms 123256 KB Output is correct
12 Correct 582 ms 123256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 335 ms 110356 KB Output is correct
15 Correct 67 ms 8696 KB Output is correct
16 Correct 1731 ms 125108 KB Output is correct
17 Correct 616 ms 122872 KB Output is correct
18 Correct 616 ms 122616 KB Output is correct

Subtask #4
0 / 39.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 3 ms 768 KB Output is correct
4 Correct 12 ms 1920 KB Output is correct
5 Correct 12 ms 1920 KB Output is correct
6 Correct 12 ms 1920 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 320 ms 110208 KB Output is correct
9 Correct 432 ms 51192 KB Output is correct
10 Correct 1597 ms 125176 KB Output is correct
11 Correct 596 ms 123128 KB Output is correct
12 Correct 617 ms 123256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 336 ms 110300 KB Output is correct
15 Correct 67 ms 8700 KB Output is correct
16 Correct 1585 ms 125076 KB Output is correct
17 Correct 603 ms 122872 KB Output is correct
18 Correct 611 ms 122744 KB Output is correct
19 Correct 2916 ms 184384 KB Output is correct
20 Correct 2953 ms 194508 KB Output is correct
21 Execution timed out 3036 ms 194684 KB Time limit exceeded
22 Halted 0 ms 0 KB -