oj.uz

Submission #1010037

# Submission time Handle Problem Language Result Execution time Memory
1010037 2024-06-28T09:27:30 Z stdfloat Wall (IOI14_wall) C++17
100 / 100
 1375 ms 193360 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

#define ff  first
#define ss  second
#define pii pair<int, int>

vector<int> st;

vector<pair<pii, pii>> lz;

void Lz(int nd, pii p) {
    if ((lz[nd].ff.ff == 1 && p.ff == 1 && lz[nd].ff.ss <= p.ss) || (lz[nd].ff.ff == 2 && p.ff == 2 && lz[nd].ff.ss >= p.ss)) lz[nd].ff = {-1, -1};
    if ((lz[nd].ss.ff == 1 && p.ff == 1 && lz[nd].ss.ss <= p.ss) || (lz[nd].ss.ff == 2 && p.ff == 2 && lz[nd].ss.ss >= p.ss)) lz[nd].ss = {-1, -1};

    if (lz[nd].ff == (pii){-1, -1}) swap(lz[nd].ff, lz[nd].ss);

    if (lz[nd].ff.ff == p.ff || lz[nd].ss.ff == p.ff) return;

    if (lz[nd].ff == (pii){-1, -1}) lz[nd].ff = p;
    else if (lz[nd].ss == (pii){-1, -1}) lz[nd].ss = p;
    
    if (lz[nd].ss != (pii){-1, -1}) {
        if (lz[nd].ff.ff == 2) lz[nd].ff.ss = max(lz[nd].ff.ss, lz[nd].ss.ss);
        else lz[nd].ff.ss = min(lz[nd].ff.ss, lz[nd].ss.ss);
    }
}

void LZ(int nd, int l, int r) {
    if (lz[nd].ff.ff == 1) st[nd] = max(st[nd], lz[nd].ff.ss);
    else if (lz[nd].ff.ff == 2) st[nd] = min(st[nd], lz[nd].ff.ss);
    
    if (lz[nd].ss.ff == 1) st[nd] = max(st[nd], lz[nd].ss.ss);
    else if (lz[nd].ss.ff == 2) st[nd] = min(st[nd], lz[nd].ss.ss);

    if (l < r) {
        int ch = (nd << 1) + 1;
        if (lz[nd].ff != (pii){-1, -1}) {
            Lz(ch, lz[nd].ff); Lz(ch + 1, lz[nd].ff);
        }
        if (lz[nd].ss != (pii){-1, -1}) {
            Lz(ch, lz[nd].ss); Lz(ch + 1, lz[nd].ss);
        }
    }

    lz[nd].ff = lz[nd].ss = {-1, -1};
}

int upd(int nd, int l, int r, int x, int y, int op, int h) {
    LZ(nd, l, r);

    if (r < x || y < l) return st[nd];

    if (x <= l && r <= y) {
        Lz(nd, {op, h}); LZ(nd, l, r);
        return st[nd];
    }

    int ch = (nd << 1) + 1, md = (l + r) >> 1;
    return st[nd] = max(upd(ch, l, md, x, y, op, h), upd(ch + 1, md + 1, r, x, y, op, h));
}

int fnd(int nd, int l, int r, int x) {
    LZ(nd, l, r);

    if (r < x || x < l) return 0;

    if (l == r) return st[nd];

    int ch = (nd << 1) + 1, md = (l + r) >> 1;
    return max(fnd(ch, l, md, x), fnd(ch + 1, md + 1, r, x));
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]) {
    st.assign(n << 2, 0);
    lz.assign(n << 2, {});

    for (auto &i : lz) {
        i.ff = i.ss = {-1, -1};
    }

    for (int i = 0; i < k; i++) {
        upd(0, 0, n - 1, l[i], r[i], op[i], h[i]);
    }

    for (int i = 0; i < n; i++) {
        fh[i] = fnd(0, 0, n - 1, i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 15 ms 1372 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 11 ms 1372 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 86 ms 13972 KB Output is correct
3 Correct 264 ms 8784 KB Output is correct
4 Correct 828 ms 26192 KB Output is correct
5 Correct 273 ms 27272 KB Output is correct
6 Correct 259 ms 25684 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 11 ms 1372 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 6 ms 1460 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 91 ms 14044 KB Output is correct
9 Correct 241 ms 8788 KB Output is correct
10 Correct 799 ms 26208 KB Output is correct
11 Correct 252 ms 27272 KB Output is correct
12 Correct 263 ms 25680 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 100 ms 13920 KB Output is correct
15 Correct 58 ms 2896 KB Output is correct
16 Correct 1121 ms 26468 KB Output is correct
17 Correct 274 ms 25948 KB Output is correct
18 Correct 271 ms 25936 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 11 ms 1436 KB Output is correct
5 Correct 6 ms 1372 KB Output is correct
6 Correct 6 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 87 ms 13860 KB Output is correct
9 Correct 250 ms 8944 KB Output is correct
10 Correct 855 ms 26448 KB Output is correct
11 Correct 267 ms 27220 KB Output is correct
12 Correct 238 ms 25680 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 87 ms 13940 KB Output is correct
15 Correct 56 ms 2916 KB Output is correct
16 Correct 1141 ms 26468 KB Output is correct
17 Correct 291 ms 25996 KB Output is correct
18 Correct 257 ms 25888 KB Output is correct
19 Correct 1276 ms 193252 KB Output is correct
20 Correct 1270 ms 190640 KB Output is correct
21 Correct 1262 ms 193360 KB Output is correct
22 Correct 1250 ms 191040 KB Output is correct
23 Correct 1375 ms 190812 KB Output is correct
24 Correct 1302 ms 190800 KB Output is correct
25 Correct 1250 ms 190620 KB Output is correct
26 Correct 1209 ms 193204 KB Output is correct
27 Correct 1227 ms 193180 KB Output is correct
28 Correct 1254 ms 190616 KB Output is correct
29 Correct 1267 ms 190800 KB Output is correct
30 Correct 1177 ms 190800 KB Output is correct