oj.uz

Submission #349281

# Submission time Handle Problem Language Result Execution time Memory
349281 2021-01-17T10:23:07 Z parsabahrami Wall (IOI14_wall) C++17
100 / 100
 1040 ms 100976 KB 
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          id << 1
#define rc                          lc | 1

const int N = 2e6 + 10;
int mx[N << 2], mn[N << 2], lz[N << 2], _n, k;

void shift(int id, int l, int r) {
    if (lz[id] < 0) return;
    mx[id] = mn[id] = lz[id];
    if (r - l > 1) {
        lz[lc] = lz[rc] = lz[id];
    }
    lz[id] = -1;
}

void setmin(int ql, int qr, int x, int id = 1, int l = 0, int r = _n) {
    shift(id, l, r);
    if (qr <= l || r <= ql || mx[id] <= x) return;
    if (ql <= l && r <= qr && mn[id] >= x) {
        lz[id] = x; 
        return shift(id, l, r);
    }  
    int mid = (l + r) >> 1;
    setmin(ql, qr, x, lc, l, mid);
    setmin(ql, qr, x, rc, mid, r);
    mn[id] = min(mn[lc], mn[rc]);
    mx[id] = max(mx[lc], mx[rc]);
}

void setmax(int ql, int qr, int x, int id = 1, int l = 0, int r = _n) {
    shift(id, l, r);
    if (qr <= l || r <= ql || mn[id] >= x) return;
    if (ql <= l && r <= qr && mx[id] <= x) {
        lz[id] = x; 
        return shift(id, l, r);
    }  
    int mid = (l + r) >> 1;
    setmax(ql, qr, x, lc, l, mid);
    setmax(ql, qr, x, rc, mid, r);
    mn[id] = min(mn[lc], mn[rc]);
    mx[id] = max(mx[lc], mx[rc]);
}

int print(int pos, int id = 1, int l = 0, int r = _n) {
    shift(id, l, r);
    if (r - l < 2) {
        return mx[id];
    }
    int mid = (l + r) >> 1;
    if (pos < mid) return print(pos, lc, l, mid);
    else return print(pos, rc, mid, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	memset(lz, -1, sizeof lz);
    _n = n;
    for (int i = 0; i < k; i++) {
        int t = op[i], l = left[i], r = right[i], h = height[i];
        if (t == 1) setmax(l, r + 1, h);
        else setmin(l, r + 1, h);
    }
    for (int i = 0; i < n; i++) finalHeight[i] = print(i);
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31596 KB Output is correct
2 Correct 21 ms 31724 KB Output is correct
3 Correct 19 ms 31724 KB Output is correct
4 Correct 24 ms 32236 KB Output is correct
5 Correct 24 ms 32108 KB Output is correct
6 Correct 24 ms 32108 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31596 KB Output is correct
2 Correct 175 ms 45292 KB Output is correct
3 Correct 103 ms 39276 KB Output is correct
4 Correct 229 ms 52028 KB Output is correct
5 Correct 240 ms 52992 KB Output is correct
6 Correct 264 ms 51200 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31596 KB Output is correct
2 Correct 18 ms 31724 KB Output is correct
3 Correct 18 ms 31724 KB Output is correct
4 Correct 23 ms 32236 KB Output is correct
5 Correct 23 ms 32108 KB Output is correct
6 Correct 22 ms 32108 KB Output is correct
7 Correct 17 ms 31596 KB Output is correct
8 Correct 174 ms 45292 KB Output is correct
9 Correct 100 ms 39356 KB Output is correct
10 Correct 227 ms 51820 KB Output is correct
11 Correct 238 ms 52844 KB Output is correct
12 Correct 265 ms 51180 KB Output is correct
13 Correct 16 ms 31596 KB Output is correct
14 Correct 191 ms 45320 KB Output is correct
15 Correct 51 ms 33344 KB Output is correct
16 Correct 568 ms 51948 KB Output is correct
17 Correct 369 ms 51372 KB Output is correct
18 Correct 370 ms 51436 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31596 KB Output is correct
2 Correct 19 ms 31724 KB Output is correct
3 Correct 18 ms 31724 KB Output is correct
4 Correct 23 ms 32236 KB Output is correct
5 Correct 22 ms 32108 KB Output is correct
6 Correct 23 ms 32108 KB Output is correct
7 Correct 17 ms 31596 KB Output is correct
8 Correct 184 ms 45292 KB Output is correct
9 Correct 104 ms 39276 KB Output is correct
10 Correct 230 ms 51820 KB Output is correct
11 Correct 248 ms 52844 KB Output is correct
12 Correct 285 ms 51180 KB Output is correct
13 Correct 16 ms 31596 KB Output is correct
14 Correct 178 ms 45292 KB Output is correct
15 Correct 56 ms 33388 KB Output is correct
16 Correct 563 ms 52004 KB Output is correct
17 Correct 365 ms 51436 KB Output is correct
18 Correct 373 ms 51436 KB Output is correct
19 Correct 1016 ms 100928 KB Output is correct
20 Correct 1040 ms 98540 KB Output is correct
21 Correct 1018 ms 100976 KB Output is correct
22 Correct 999 ms 98348 KB Output is correct
23 Correct 1002 ms 98500 KB Output is correct
24 Correct 1031 ms 98436 KB Output is correct
25 Correct 1006 ms 98336 KB Output is correct
26 Correct 1008 ms 100972 KB Output is correct
27 Correct 1006 ms 100972 KB Output is correct
28 Correct 1004 ms 98412 KB Output is correct
29 Correct 992 ms 98540 KB Output is correct
30 Correct 1002 ms 98412 KB Output is correct