oj.uz

Submission #453664

# Submission time Handle Problem Language Result Execution time Memory
453664 2021-08-04T13:54:31 Z ponytail Wall (IOI14_wall) C++17
100 / 100
 1451 ms 77524 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int MAXN = 2e6 + 10;
struct node{
    int Min, Max;
} a[4*MAXN];
void update(int l,int r,int constl,int constr,int idx,int val,string type){
    if(l<=constl && constr<=r){
        if(type == "ADD"){
            a[idx].Min = max(a[idx].Min, val);
            a[idx].Max = max(a[idx].Max, val);
        }
        else{
            a[idx].Min = min(a[idx].Min, val);
            a[idx].Max = min(a[idx].Max, val);
        }
        return;
    }
    int mid = (constl+constr)/2;
    //Lazy propagation: Remember to return a[idx].Min and a[idx].Max into initial state
    a[2*idx+1].Min = max(a[2*idx+1].Min, a[idx].Max);
    a[2*idx+1].Max = max(a[2*idx+1].Max, a[idx].Max);
    a[2*idx+2].Min = max(a[2*idx+2].Min, a[idx].Max);
    a[2*idx+2].Max = max(a[2*idx+2].Max, a[idx].Max);
    a[2*idx+1].Min = min(a[2*idx+1].Min, a[idx].Min);
    a[2*idx+1].Max = min(a[2*idx+1].Max, a[idx].Min);
    a[2*idx+2].Min = min(a[2*idx+2].Min, a[idx].Min);
    a[2*idx+2].Max = min(a[2*idx+2].Max, a[idx].Min);
    a[idx].Min = 1e9;
    a[idx].Max = 0;
    if(mid<l || r<constl) update(l, r, mid+1, constr, 2*idx+2, val, type);
    else if(constr<l || r<mid+1) update(l, r, constl, mid, 2*idx+1, val, type);
    else{
        update(l, r, constl, mid, 2*idx+1, val, type);
        update(l, r, mid+1, constr,  2*idx+2, val, type);
    }
}
int N;
vector<int> ans;
void query(int l,int r,int idx){
    if(l == r){
        if(l >= 1 && r <= N) ans.push_back(a[idx].Max);
        return;
    }
    //Lazy propagation during query too
    a[2*idx+1].Min = max(a[2*idx+1].Min, a[idx].Max);
    a[2*idx+1].Max = max(a[2*idx+1].Max, a[idx].Max);
    a[2*idx+2].Min = max(a[2*idx+2].Min, a[idx].Max);
    a[2*idx+2].Max = max(a[2*idx+2].Max, a[idx].Max);
    a[2*idx+1].Min = min(a[2*idx+1].Min, a[idx].Min);
    a[2*idx+1].Max = min(a[2*idx+1].Max, a[idx].Min);
    a[2*idx+2].Min = min(a[2*idx+2].Min, a[idx].Min);
    a[2*idx+2].Max = min(a[2*idx+2].Max, a[idx].Min);
    a[idx].Min = 1e9;
    a[idx].Max = 0;
    int mid = (l+r) / 2;
    query(l, mid, 2*idx+1);
    query(mid+1, r, 2*idx+2);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N = n;
    //initialize all Min's to 1e9
    for(int i=0; i<MAXN; i++){
        a[i].Min = 1e9;
        a[i].Max = 0;
    }
    for(int i=0; i<k; i++){
        int ops = op[i];
        int L, R, h; 
        L = left[i], R = right[i], h = height[i];
        L++; R++;
        if(ops == 1){
            update(L, R, 0, MAXN-1, 0, h, "ADD");
        }
        else{
            update(L, R, 0, MAXN-1, 0, h, "REM");
        }
    }
    query(0, MAXN-1, 0); 
    for(int i=0; i<N; i++) finalHeight[i] = ans[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 33048 KB Output is correct
2 Correct 49 ms 33188 KB Output is correct
3 Correct 51 ms 33136 KB Output is correct
4 Correct 67 ms 33384 KB Output is correct
5 Correct 54 ms 33348 KB Output is correct
6 Correct 54 ms 33428 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 33076 KB Output is correct
2 Correct 526 ms 46680 KB Output is correct
3 Correct 408 ms 40428 KB Output is correct
4 Correct 1142 ms 51644 KB Output is correct
5 Correct 684 ms 52712 KB Output is correct
6 Correct 619 ms 51108 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 33068 KB Output is correct
2 Correct 49 ms 33164 KB Output is correct
3 Correct 48 ms 33116 KB Output is correct
4 Correct 64 ms 33468 KB Output is correct
5 Correct 52 ms 33476 KB Output is correct
6 Correct 55 ms 33452 KB Output is correct
7 Correct 54 ms 33004 KB Output is correct
8 Correct 588 ms 46768 KB Output is correct
9 Correct 427 ms 40480 KB Output is correct
10 Correct 1050 ms 51644 KB Output is correct
11 Correct 631 ms 52728 KB Output is correct
12 Correct 613 ms 51048 KB Output is correct
13 Correct 44 ms 33096 KB Output is correct
14 Correct 548 ms 46788 KB Output is correct
15 Correct 101 ms 34500 KB Output is correct
16 Correct 1063 ms 52108 KB Output is correct
17 Correct 626 ms 51388 KB Output is correct
18 Correct 627 ms 51336 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 33096 KB Output is correct
2 Correct 50 ms 33136 KB Output is correct
3 Correct 48 ms 33252 KB Output is correct
4 Correct 55 ms 33376 KB Output is correct
5 Correct 54 ms 33360 KB Output is correct
6 Correct 54 ms 33496 KB Output is correct
7 Correct 44 ms 33048 KB Output is correct
8 Correct 560 ms 46768 KB Output is correct
9 Correct 414 ms 40484 KB Output is correct
10 Correct 1064 ms 51640 KB Output is correct
11 Correct 641 ms 52752 KB Output is correct
12 Correct 682 ms 51080 KB Output is correct
13 Correct 44 ms 33096 KB Output is correct
14 Correct 524 ms 46768 KB Output is correct
15 Correct 114 ms 34396 KB Output is correct
16 Correct 1067 ms 51956 KB Output is correct
17 Correct 647 ms 51292 KB Output is correct
18 Correct 670 ms 51332 KB Output is correct
19 Correct 1379 ms 77524 KB Output is correct
20 Correct 1411 ms 74892 KB Output is correct
21 Correct 1386 ms 77384 KB Output is correct
22 Correct 1451 ms 75024 KB Output is correct
23 Correct 1367 ms 74960 KB Output is correct
24 Correct 1403 ms 74956 KB Output is correct
25 Correct 1385 ms 74904 KB Output is correct
26 Correct 1388 ms 77436 KB Output is correct
27 Correct 1388 ms 77436 KB Output is correct
28 Correct 1393 ms 74916 KB Output is correct
29 Correct 1420 ms 75036 KB Output is correct
30 Correct 1421 ms 74920 KB Output is correct