oj.uz

Submission #252464

# Submission time Handle Problem Language Result Execution time Memory
252464 2020-07-25T15:54:53 Z eohomegrownapps Wall (IOI14_wall) C++14
24 / 100
 1518 ms 132472 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
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 12 ms 1920 KB Output is correct
5 Correct 11 ms 1920 KB Output is correct
6 Incorrect 11 ms 1920 KB Output isn't correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 322 ms 113756 KB Output is correct
3 Correct 414 ms 53880 KB Output is correct
4 Correct 1518 ms 132472 KB Output is correct
5 Correct 599 ms 131064 KB Output is correct
6 Correct 571 ms 129528 KB Output is correct

Subtask #3
0 / 29.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 14 ms 1920 KB Output is correct
5 Correct 12 ms 1920 KB Output is correct
6 Incorrect 12 ms 1920 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 39.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 12 ms 1976 KB Output is correct
6 Incorrect 12 ms 1920 KB Output isn't correct
7 Halted 0 ms 0 KB -