oj.uz

Submission #101863

# Submission time Handle Problem Language Result Execution time Memory
101863 2019-03-20T15:04:57 Z eriksuenderhauf Wall (IOI14_wall) C++11
100 / 100
 1955 ms 102476 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "wall.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 2e6 + 5;
const double eps = 1e-9;
int seg[MAXN*4][2], lazy[MAXN*4][2];

void build(int l, int r, int k) {
    lazy[k][0] = lazy[k][1] = -1;
    if (l == r) {
        seg[k][0] = seg[k][1] = 0;
        return;
    }
    int m = (l + r) / 2;
    build(l, m, k*2);
    build(m+1, r, k*2+1);
    seg[k][0] = min(seg[k*2][0], seg[k*2+1][0]);
    seg[k][1] = max(seg[k*2][1], seg[k*2+1][1]);
}

void prop(int l, int r, int k) {
    if (lazy[k][0] != -1) {
        seg[k][0] = max(seg[k][0],lazy[k][0]);
        seg[k][1] = max(seg[k][1],lazy[k][0]);
    }
    if (lazy[k][1] != -1) {
        seg[k][0] = min(seg[k][0],lazy[k][1]);
        seg[k][1] = min(seg[k][1],lazy[k][1]);
    }
    if (l != r && lazy[k][0] != -1) {
        if (lazy[k*2][0] == -1 || lazy[k][0] > lazy[k*2][0])
            lazy[k*2][0] = lazy[k][0];
        if (lazy[k*2][1] != -1 && lazy[k*2][1] < lazy[k][0])
            lazy[k*2][1] = lazy[k][0];
        if (lazy[k*2+1][0] == -1 || lazy[k][0] > lazy[k*2+1][0])
            lazy[k*2+1][0] = lazy[k][0];
        if (lazy[k*2+1][1] != -1 && lazy[k*2+1][1] < lazy[k][0])
            lazy[k*2+1][1] = lazy[k][0];
    }
    if (l != r && lazy[k][1] != -1) {
        if (lazy[k*2][1] == -1 || lazy[k][1] < lazy[k*2][1])
            lazy[k*2][1] = lazy[k][1];
        if (lazy[k*2][0] != -1 && lazy[k*2][0] > lazy[k][1])
            lazy[k*2][0] = lazy[k][1];
        if (lazy[k*2+1][1] == -1 || lazy[k][1] < lazy[k*2+1][1])
            lazy[k*2+1][1] = lazy[k][1];
        if (lazy[k*2+1][0] != -1 && lazy[k*2+1][0] > lazy[k][1])
            lazy[k*2+1][0] = lazy[k][1];
    }
    lazy[k][0] = -1;
    lazy[k][1] = -1;
}

void upd(int l, int r, int k, int a, int b, int v, int t) {
    if (r < a || b < l) return;
    prop(l, r, k);
    if (a <= l && r <= b) {
        lazy[k][t] = v;
        prop(l, r, k);
        return;
    }
    int m = (l+r) / 2;
    upd(l, m, k*2, a, b, v, t);
    upd(m+1, r, k*2+1, a, b, v, t);
    seg[k][0] = min(seg[k*2][0], seg[k*2+1][0]);
    seg[k][1] = max(seg[k*2][1], seg[k*2+1][1]);
}

int qry(int l, int r, int k, int a) {
    prop(l, r, k);
    if (a <= l && r <= a) {
        return seg[k][0];
    }
    int m = (l+r) / 2;
    int ret = -1;
    if (a <= m)
        ret = qry(l, m, k*2, a);
    else
        ret = qry(m+1, r, k*2+1, a);
    seg[k][0] = min(min(seg[k*2][0], seg[k*2+1][0]),min(seg[k*2][1], seg[k*2+1][1]));
    seg[k][1] = max(max(seg[k*2][0], seg[k*2+1][0]),max(seg[k*2][1], seg[k*2+1][1]));
    return ret;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    // adding phase: set minimum to a given value
    // removing phase: set maximum to a given value
    build(0, n - 1, 1);
    for (int i = 0; i < k; i++) {
        upd(0, n - 1, 1, left[i], right[i], height[i], op[i]-1);
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = qry(0, n - 1, 1, i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 16 ms 1152 KB Output is correct
5 Correct 15 ms 1144 KB Output is correct
6 Correct 10 ms 1152 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 179 ms 14056 KB Output is correct
3 Correct 423 ms 8544 KB Output is correct
4 Correct 1371 ms 22492 KB Output is correct
5 Correct 520 ms 23544 KB Output is correct
6 Correct 458 ms 21952 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 21 ms 1144 KB Output is correct
5 Correct 17 ms 1152 KB Output is correct
6 Correct 11 ms 1152 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 174 ms 14072 KB Output is correct
9 Correct 340 ms 8568 KB Output is correct
10 Correct 1129 ms 22520 KB Output is correct
11 Correct 497 ms 23672 KB Output is correct
12 Correct 368 ms 22012 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 184 ms 13992 KB Output is correct
15 Correct 73 ms 2556 KB Output is correct
16 Correct 1397 ms 22776 KB Output is correct
17 Correct 428 ms 22264 KB Output is correct
18 Correct 424 ms 22212 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 16 ms 1152 KB Output is correct
5 Correct 10 ms 1152 KB Output is correct
6 Correct 12 ms 1152 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 200 ms 13944 KB Output is correct
9 Correct 348 ms 8568 KB Output is correct
10 Correct 1016 ms 22476 KB Output is correct
11 Correct 454 ms 23656 KB Output is correct
12 Correct 465 ms 21908 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 185 ms 14140 KB Output is correct
15 Correct 73 ms 2552 KB Output is correct
16 Correct 1352 ms 22776 KB Output is correct
17 Correct 408 ms 22264 KB Output is correct
18 Correct 407 ms 22204 KB Output is correct
19 Correct 1704 ms 102300 KB Output is correct
20 Correct 1693 ms 99960 KB Output is correct
21 Correct 1524 ms 102256 KB Output is correct
22 Correct 1663 ms 99888 KB Output is correct
23 Correct 1808 ms 99724 KB Output is correct
24 Correct 1647 ms 99836 KB Output is correct
25 Correct 1586 ms 99772 KB Output is correct
26 Correct 1697 ms 102476 KB Output is correct
27 Correct 1955 ms 102292 KB Output is correct
28 Correct 1772 ms 99792 KB Output is correct
29 Correct 1656 ms 99868 KB Output is correct
30 Correct 1604 ms 99748 KB Output is correct