oj.uz

Submission #623362

# Submission time Handle Problem Language Result Execution time Memory
623362 2022-08-05T13:53:18 Z M_W Wall (IOI14_wall) C++17
100 / 100
 844 ms 132132 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define ii pair<int, int>
using namespace std;

int t[2000002 << 2][2], lazy[2000002 << 2][2]; // lower, upper

void push(int v){
    // Do something
    if(lazy[v][0] == 0 && lazy[v][1] == INT_MAX) return;
    t[v * 2][0] = max(t[v * 2][0], lazy[v][0]);
    t[v * 2 + 1][0] = max(t[v * 2 + 1][0], lazy[v][0]);
    t[v * 2][1] = max(t[v * 2][1], lazy[v][0]);
    t[v * 2 + 1][1] = max(t[v * 2 + 1][1], lazy[v][0]);

    lazy[v * 2][0] = max(lazy[v * 2][0], lazy[v][0]);
    lazy[v * 2 + 1][0] = max(lazy[v * 2 + 1][0], lazy[v][0]);
    lazy[v * 2][1] = max(lazy[v * 2][1], lazy[v][0]);
    lazy[v * 2 + 1][1] = max(lazy[v * 2 + 1][1], lazy[v][0]);

    t[v * 2][0] = min(t[v * 2][0], lazy[v][1]);
    t[v * 2 + 1][0] = min(t[v * 2 + 1][0], lazy[v][1]);
    t[v * 2][1] = min(t[v * 2][1], lazy[v][1]);
    t[v * 2 + 1][1] = min(t[v * 2 + 1][1], lazy[v][1]);

    lazy[v * 2][0] = min(lazy[v * 2][0], lazy[v][1]);
    lazy[v * 2 + 1][0] = min(lazy[v * 2 + 1][0], lazy[v][1]);
    lazy[v * 2][1] = min(lazy[v * 2][1], lazy[v][1]);
    lazy[v * 2 + 1][1] = min(lazy[v * 2 + 1][1], lazy[v][1]);

    lazy[v][0] = 0; lazy[v][1] = INT_MAX;
}

void ins(int v, int tl, int tr, int l, int r, int type, int val){
    if(l > r) return;
    if(tl == l && tr == r){
        if(type == 1){
            // shift lower
            t[v][0] = max(t[v][0], val);
            t[v][1] = max(t[v][1], val);

            lazy[v][0] = max(lazy[v][0], val);
            lazy[v][1] = max(lazy[v][1], val);
        }
        else{
            // shift upper;
            t[v][0] = min(t[v][0], val);
            t[v][1] = min(t[v][1], val);

            lazy[v][0] = min(lazy[v][0], val);
            lazy[v][1] = min(lazy[v][1], val);
        }
        return;
    }
    push(v);
    int tm = (tl + tr) >> 1;
    ins(v * 2, tl, tm, l, min(r, tm), type, val);
    ins(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, type, val);

    t[v][0] = min(t[v * 2][0], t[v * 2 + 1][0]);
    t[v][1] = max(t[v * 2][1], t[v * 2 + 1][1]);
}

int query(int v, int tl, int tr, int pos){
    if(tl == pos && tr == pos) return t[v][0];
    push(v);

    int tm = (tl + tr) >> 1;
    if(pos <= tm) return query(v * 2, tl, tm, pos);
    else return query(v * 2 + 1, tm + 1, tr, pos);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i <= n << 2; i++) lazy[i][1] = INT_MAX;
    for(int i = 0; i < k; i++){
      ins(1, 0, n - 1, left[i], right[i], op[i], height[i]);
    }
    for(int i = 0; i < n; i++){
      finalHeight[i] = query(1, 0, n - 1, i);
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 10 ms 1108 KB Output is correct
5 Correct 8 ms 1108 KB Output is correct
6 Correct 6 ms 1108 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 138 ms 13876 KB Output is correct
3 Correct 190 ms 8480 KB Output is correct
4 Correct 619 ms 23452 KB Output is correct
5 Correct 268 ms 24508 KB Output is correct
6 Correct 262 ms 22940 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1148 KB Output is correct
5 Correct 6 ms 1084 KB Output is correct
6 Correct 6 ms 1108 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 138 ms 14024 KB Output is correct
9 Correct 205 ms 8488 KB Output is correct
10 Correct 583 ms 23516 KB Output is correct
11 Correct 274 ms 24536 KB Output is correct
12 Correct 260 ms 23048 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 138 ms 13892 KB Output is correct
15 Correct 39 ms 2572 KB Output is correct
16 Correct 628 ms 23700 KB Output is correct
17 Correct 326 ms 23128 KB Output is correct
18 Correct 291 ms 23084 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 132 ms 13952 KB Output is correct
9 Correct 190 ms 8476 KB Output is correct
10 Correct 580 ms 23448 KB Output is correct
11 Correct 276 ms 24492 KB Output is correct
12 Correct 291 ms 22952 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 132 ms 13896 KB Output is correct
15 Correct 35 ms 2536 KB Output is correct
16 Correct 612 ms 23700 KB Output is correct
17 Correct 268 ms 23180 KB Output is correct
18 Correct 263 ms 23156 KB Output is correct
19 Correct 788 ms 132124 KB Output is correct
20 Correct 831 ms 129584 KB Output is correct
21 Correct 805 ms 132056 KB Output is correct
22 Correct 810 ms 129636 KB Output is correct
23 Correct 844 ms 129644 KB Output is correct
24 Correct 834 ms 129532 KB Output is correct
25 Correct 836 ms 129584 KB Output is correct
26 Correct 835 ms 132132 KB Output is correct
27 Correct 810 ms 132048 KB Output is correct
28 Correct 828 ms 129556 KB Output is correct
29 Correct 828 ms 129624 KB Output is correct
30 Correct 828 ms 129744 KB Output is correct