oj.uz

Submission #92511

# Submission time Handle Problem Language Result Execution time Memory
92511 2019-01-03T08:21:10 Z easrui Wall (IOI14_wall) C++14
100 / 100
 649 ms 77304 KB 
#include <bits/stdc++.h>
#define vl first
#define vr second
//#include "wall.h"
using namespace std;
typedef pair<int,int> pii;
const int MN = 2e6+5;

pii ST[4*MN];
int finH[MN];

void init(int s, int e, int pos)
{
    ST[pos].vl = 0;
    ST[pos].vr = MN;
    if(s==e) return;
    int m = (s+e)/2;
    init(s,m,2*pos);
    init(m+1,e,2*pos+1);
}

void fin(int s, int e, int pos)
{
    int L = ST[pos].vl, R = ST[pos].vr;
    if(s==e){
        finH[s] = L;
        return;
    }
    int m = (s+e)/2;
    ST[2*pos].vl = max(ST[2*pos].vl,L);
    ST[2*pos].vr = max(ST[2*pos].vr,L);
    ST[2*pos].vl = min(ST[2*pos].vl,R);
    ST[2*pos].vr = min(ST[2*pos].vr,R);
    ST[2*pos+1].vl = max(ST[2*pos+1].vl,L);
    ST[2*pos+1].vr = max(ST[2*pos+1].vr,L);
    ST[2*pos+1].vl = min(ST[2*pos+1].vl,R);
    ST[2*pos+1].vr = min(ST[2*pos+1].vr,R);
    fin(s, m, 2*pos);
    fin(m+1, e, 2*pos+1);
}

void upt(int qu, int l, int r, int h, int s, int e, int pos)
{
    if(e<l || s>r) return;
    int L = ST[pos].vl, R = ST[pos].vr;
    if(l<=s && e<=r){
        if(qu==1){
            ST[pos].vl = max(L,h);
            ST[pos].vr = max(R,h);
        }
        else{
            ST[pos].vl = min(L,h);
            ST[pos].vr = min(R,h);
        }
        return ;
    }
    int m = (s+e)/2;
    ST[2*pos].vl = max(ST[2*pos].vl,L);
    ST[2*pos].vr = max(ST[2*pos].vr,L);
    ST[2*pos].vl = min(ST[2*pos].vl,R);
    ST[2*pos].vr = min(ST[2*pos].vr,R);
    ST[2*pos+1].vl = max(ST[2*pos+1].vl,L);
    ST[2*pos+1].vr = max(ST[2*pos+1].vr,L);
    ST[2*pos+1].vl = min(ST[2*pos+1].vl,R);
    ST[2*pos+1].vr = min(ST[2*pos+1].vr,R);
    ST[pos].vl = 0;
    ST[pos].vr = MN;
    upt(qu, l, r, h, s, m, 2*pos);
    upt(qu, l, r, h, m+1, e, 2*pos+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    init(0,n-1,1);
    //cout << height[0] << '\n';
    for(int i=0; i<k; i++) upt(op[i],left[i],right[i],height[i],0,n-1,1);
    //cout << 1 << '\n';
    fin(0,n-1,1);
    for(int i=0; i<n; i++) finalHeight[i] = finH[i];
};

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 7 ms 888 KB Output is correct
5 Correct 6 ms 888 KB Output is correct
6 Correct 6 ms 888 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 148 ms 14060 KB Output is correct
3 Correct 161 ms 8184 KB Output is correct
4 Correct 466 ms 20872 KB Output is correct
5 Correct 286 ms 22048 KB Output is correct
6 Correct 278 ms 20316 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 7 ms 892 KB Output is correct
5 Correct 6 ms 888 KB Output is correct
6 Correct 6 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 147 ms 14172 KB Output is correct
9 Correct 160 ms 8056 KB Output is correct
10 Correct 457 ms 20952 KB Output is correct
11 Correct 285 ms 21972 KB Output is correct
12 Correct 278 ms 20336 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 149 ms 14024 KB Output is correct
15 Correct 27 ms 2296 KB Output is correct
16 Correct 472 ms 21112 KB Output is correct
17 Correct 279 ms 20572 KB Output is correct
18 Correct 281 ms 20472 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 7 ms 888 KB Output is correct
5 Correct 6 ms 888 KB Output is correct
6 Correct 6 ms 888 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 147 ms 14072 KB Output is correct
9 Correct 164 ms 8060 KB Output is correct
10 Correct 465 ms 20904 KB Output is correct
11 Correct 282 ms 22152 KB Output is correct
12 Correct 270 ms 20344 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 148 ms 14072 KB Output is correct
15 Correct 27 ms 2168 KB Output is correct
16 Correct 446 ms 21212 KB Output is correct
17 Correct 281 ms 20492 KB Output is correct
18 Correct 280 ms 20472 KB Output is correct
19 Correct 639 ms 77304 KB Output is correct
20 Correct 634 ms 74960 KB Output is correct
21 Correct 649 ms 77300 KB Output is correct
22 Correct 633 ms 74872 KB Output is correct
23 Correct 632 ms 74744 KB Output is correct
24 Correct 632 ms 74872 KB Output is correct
25 Correct 634 ms 74904 KB Output is correct
26 Correct 632 ms 77200 KB Output is correct
27 Correct 640 ms 77112 KB Output is correct
28 Correct 620 ms 74744 KB Output is correct
29 Correct 638 ms 74740 KB Output is correct
30 Correct 622 ms 74768 KB Output is correct