oj.uz

Submission #290611

# Submission time Handle Problem Language Result Execution time Memory
290611 2020-09-04T07:13:46 Z georgerapeanu Wall (IOI14_wall) C++11
100 / 100
 966 ms 69624 KB 
#include "wall.h"
#pragma once
#include <algorithm>
#include <cstdio>

using namespace std;

const int NMAX = 2e6;

pair<int,int> aint[4 * NMAX + 5];

void prop(pair<int,int> &a,pair<int,int> &b){
    if(a.second < b.first){
        b = {a.second,a.second};
    }
    else if(b.second < a.first){
        b = {a.first,a.first};
    }
    else{
        b = {max(a.first,b.first),min(a.second,b.second)};
    }
}

void propag(int nod,int st,int dr){
    if(st == dr){
        return ;
    }

    prop(aint[nod],aint[nod * 2]);
    prop(aint[nod],aint[nod * 2 + 1]);
    aint[nod] = {0,1e5};
}

void build(int nod,int st,int dr){
    aint[nod] = {0,1e5};

    if(st == dr){
        return ;
    }

    int mid = (st + dr) / 2;

    build(nod * 2,st,mid);
    build(nod * 2 + 1,mid + 1,dr);
}

void update(int nod,int st,int dr,int op,int l,int r,int h){
    propag(nod,st,dr);
    if(dr < l || st > r){
        return ;
    }

    if(l <= st && dr <= r){
        pair<int,int> tmp = {0,1e5};
        if(op == 1){
            tmp.first = h;
        }
        else{
            tmp.second = h;
        }
        prop(tmp,aint[nod]);
        return ;
    }

    int mid = (st + dr) / 2;

    update(nod * 2,st,mid,op,l,r,h);
    update(nod * 2 + 1,mid + 1,dr,op,l,r,h);
}

void dfs(int nod,int st,int dr,int ans[]){
    propag(nod,st,dr);
    if(st == dr){
        ans[st - 1] = aint[nod].first;
        return ;
    }

    int mid = (st + dr) / 2;

    dfs(nod * 2,st,mid,ans);
    dfs(nod * 2 + 1,mid + 1,dr,ans);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    
    build(1,1,n);
    for(int i = 0;i < k;i++){
        update(1,1,n,op[i],left[i] + 1,right[i] + 1,height[i]);
    }

    dfs(1,1,n,finalHeight);
}

Compilation message

wall.cpp:2:9: warning: #pragma once in main file
    2 | #pragma once
      |         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 170 ms 10616 KB Output is correct
3 Correct 221 ms 6816 KB Output is correct
4 Correct 637 ms 13144 KB Output is correct
5 Correct 410 ms 15224 KB Output is correct
6 Correct 388 ms 15224 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 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 171 ms 12024 KB Output is correct
9 Correct 215 ms 8060 KB Output is correct
10 Correct 627 ms 14712 KB Output is correct
11 Correct 404 ms 21624 KB Output is correct
12 Correct 386 ms 19960 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 173 ms 13944 KB Output is correct
15 Correct 43 ms 2040 KB Output is correct
16 Correct 803 ms 20732 KB Output is correct
17 Correct 394 ms 20152 KB Output is correct
18 Correct 397 ms 20216 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 169 ms 12024 KB Output is correct
9 Correct 221 ms 7980 KB Output is correct
10 Correct 624 ms 14712 KB Output is correct
11 Correct 405 ms 21540 KB Output is correct
12 Correct 384 ms 19832 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 174 ms 13944 KB Output is correct
15 Correct 43 ms 2040 KB Output is correct
16 Correct 870 ms 20728 KB Output is correct
17 Correct 407 ms 20056 KB Output is correct
18 Correct 400 ms 20152 KB Output is correct
19 Correct 948 ms 69624 KB Output is correct
20 Correct 953 ms 67192 KB Output is correct
21 Correct 950 ms 69624 KB Output is correct
22 Correct 952 ms 67064 KB Output is correct
23 Correct 963 ms 67192 KB Output is correct
24 Correct 935 ms 67064 KB Output is correct
25 Correct 949 ms 67072 KB Output is correct
26 Correct 953 ms 69624 KB Output is correct
27 Correct 966 ms 69520 KB Output is correct
28 Correct 936 ms 67064 KB Output is correct
29 Correct 958 ms 67192 KB Output is correct
30 Correct 939 ms 67192 KB Output is correct