oj.uz

Submission #474255

# Submission time Handle Problem Language Result Execution time Memory
474255 2021-09-17T15:49:19 Z ljuba Wall (IOI14_wall) C++17
100 / 100
 1125 ms 64924 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int mxN = 2e6 + 12;

const int INF = 1e9 + 12;

struct node {
    int mn, mx;
}st[4*mxN];

int n;

void build(int i = 1, int l2 = 0, int r2 = n-1) {
    st[i].mn = INF;
    st[i].mx = -INF;
    if(l2 == r2) {
        return;
    }

    int m2 = (l2 + 2) / 2;
    build(2*i, l2, m2);
    build(2*i+1, m2+1, 2);
}

inline void assignMin(int i, int x) {
    st[i].mn = min(st[i].mn, x);
    st[i].mx = min(st[i].mx, x);
}

inline void assignMax(int i, int x) {
    st[i].mn = max(st[i].mn, x);
    st[i].mx = max(st[i].mx, x);
}

inline void push(int i) {
    assignMin(2*i, st[i].mn);
    assignMax(2*i, st[i].mx);
    assignMin(2*i+1, st[i].mn);
    assignMax(2*i+1, st[i].mx);

    st[i].mn = INF;
    st[i].mx = -INF;
}

void minimum(int l1, int r1, int x, int i = 1, int l2 = 0, int r2 = n-1) {
    if(l1 <= l2 && r2 <= r1) {
        assignMin(i, x);
        return;
    }

    push(i);
    int m2 = (l2 + r2) / 2;
    if(l1 <= m2) minimum(l1, r1, x, 2*i, l2, m2);
    if(m2 < r1) minimum(l1, r1, x, 2*i+1, m2+1, r2);
}

void maximum(int l1, int r1, int x, int i = 1, int l2 = 0, int r2 = n-1) {
    if(l1 <= l2 && r2 <= r1) {
        assignMax(i, x);
        return;
    }

    push(i);
    int m2 = (l2 + r2) / 2;
    if(l1 <= m2) maximum(l1, r1, x, 2*i, l2, m2);
    if(m2 < r1) maximum(l1, r1, x, 2*i+1, m2+1, r2);
}

int query(int l1, int i = 1, int l2 = 0, int r2 = n-1) {
    if(l2 == r2) {
        assert(st[i].mn == st[i].mx);
        return st[i].mn;
    }

    push(i);
    int m2 = (l2 + r2) / 2;
    if(l1 <= m2) return query(l1, 2*i, l2, m2);
    else return query(l1, 2*i+1, m2+1, r2);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N;
    //for(int i = 0; i < n; ++i) {
        //cerr << 0 << " ";
    //}
    cerr << endl;
    for(int i = 0; i < k; ++i) {
        if(op[i] == 1) {
            maximum(left[i], right[i], height[i]);
        } else {
            minimum(left[i], right[i], height[i]);
        }

        //for(int i = 0; i < n; ++i) {
            //cerr << query(i) << " ";
        //}
        //cerr << endl;
    }

    for(int i = 0; i < n; ++i) {
        finalHeight[i] = query(i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 6 ms 780 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 167 ms 11636 KB Output is correct
3 Correct 162 ms 7744 KB Output is correct
4 Correct 449 ms 14376 KB Output is correct
5 Correct 363 ms 14936 KB Output is correct
6 Correct 301 ms 14788 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 6 ms 828 KB Output is correct
6 Correct 6 ms 756 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 164 ms 11724 KB Output is correct
9 Correct 160 ms 7752 KB Output is correct
10 Correct 449 ms 14396 KB Output is correct
11 Correct 312 ms 14808 KB Output is correct
12 Correct 300 ms 14788 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 167 ms 11676 KB Output is correct
15 Correct 35 ms 1936 KB Output is correct
16 Correct 473 ms 14680 KB Output is correct
17 Correct 301 ms 16736 KB Output is correct
18 Correct 297 ms 16704 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 9 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 7 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 170 ms 11656 KB Output is correct
9 Correct 162 ms 7728 KB Output is correct
10 Correct 451 ms 14344 KB Output is correct
11 Correct 346 ms 14804 KB Output is correct
12 Correct 298 ms 14860 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 163 ms 11652 KB Output is correct
15 Correct 36 ms 1984 KB Output is correct
16 Correct 467 ms 14616 KB Output is correct
17 Correct 302 ms 16744 KB Output is correct
18 Correct 340 ms 16792 KB Output is correct
19 Correct 1024 ms 64876 KB Output is correct
20 Correct 1125 ms 62444 KB Output is correct
21 Correct 1012 ms 64860 KB Output is correct
22 Correct 1012 ms 62320 KB Output is correct
23 Correct 1016 ms 62320 KB Output is correct
24 Correct 1041 ms 62236 KB Output is correct
25 Correct 1002 ms 62404 KB Output is correct
26 Correct 1046 ms 64924 KB Output is correct
27 Correct 1020 ms 64748 KB Output is correct
28 Correct 1049 ms 62304 KB Output is correct
29 Correct 1052 ms 62292 KB Output is correct
30 Correct 1061 ms 62244 KB Output is correct