oj.uz

Submission #674172

# Submission time Handle Problem Language Result Execution time Memory
674172 2022-12-23T11:16:19 Z kirakaminski968 Wall (IOI14_wall) C++17
100 / 100
 540 ms 69588 KB 
#include <iostream>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <functional>
#include <numeric>
#include <utility>
#include <cassert>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using pii = pair<int, int>;
#define MP make_pair
#define FF first
#define SS second
const int inf = 2000000011;
const pii def = MP(-inf, inf);
int N, Q;
pii T[8000000];
void init(int t = 1, int tl = 0, int tr = N - 1) {
    if (tl == 0 && tr == N - 1)
        T[t] = MP(0, 0);
    else 
        T[t] = def;
    if (tl == tr) return;
    int tm = (tl + tr) >> 1;
    init(t << 1, tl, tm);
    init(t << 1 | 1, tm + 1, tr);
}
pii push(pii a, pii b) {
    if (a.SS < b.FF) 
        return MP(a.SS, a.SS);
    if (b.SS < a.FF)
        return MP(a.FF, a.FF);
    return MP(max(a.FF, b.FF), min(a.SS, b.SS));
}
void pushdown(int t) {
    if (T[t] != def) {
        T[t << 1] = push(T[t], T[t << 1]);
        T[t << 1 | 1] = push(T[t], T[t << 1 | 1]);
        T[t] = def;
    }
}
void update(int l, int r, pii v, int t = 1, int tl = 0, int tr = N - 1) {
    if (r < tl || tr < l)
        return;
    if (l <= tl && tr <= r) {
        T[t] = push(v, T[t]);
        return;
    }
    if (tl != tr)
        pushdown(t);
    int tm = (tl + tr) >> 1;
    update(l, r, v, t << 1, tl, tm);
    update(l, r, v, t << 1 | 1, tm + 1, tr);
}
void pushall(int* ans, int t = 1, int tl = 0, int tr = N - 1) {
    if (tl == tr) {
        ans[tl] = T[t].FF;
        return;
    }
    else 
        pushdown(t);
    int tm = (tl + tr) >> 1;
    pushall(ans, t << 1, tl, tm);
    pushall(ans, t << 1 | 1, tm + 1, tr);
}
void buildWall(int n, int k, int* op, int* lb, int* rb, int* h, int* ans) {
    N = n, Q = k;
    init();
    for (int q = 0; q < Q; q++) {
        pii v = def;
        if (op[q] == 1)
            v.FF = h[q];
        else if (op[q] == 2)
            v.SS = h[q];
        update(lb[q], rb[q], v);
    }
    pushall(ans);
}
int n, q, op[500005], lb[500005], rb[500005], h[500005], ans[500005];

Compilation message

wall.cpp:12: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   12 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 6 ms 836 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 143 ms 13848 KB Output is correct
3 Correct 134 ms 7980 KB Output is correct
4 Correct 352 ms 20340 KB Output is correct
5 Correct 210 ms 21380 KB Output is correct
6 Correct 222 ms 19820 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 6 ms 836 KB Output is correct
5 Correct 4 ms 772 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 134 ms 13900 KB Output is correct
9 Correct 132 ms 7936 KB Output is correct
10 Correct 349 ms 20316 KB Output is correct
11 Correct 211 ms 21404 KB Output is correct
12 Correct 206 ms 19804 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 156 ms 13912 KB Output is correct
15 Correct 27 ms 2004 KB Output is correct
16 Correct 456 ms 20576 KB Output is correct
17 Correct 219 ms 20032 KB Output is correct
18 Correct 216 ms 20028 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 832 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 772 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 130 ms 13848 KB Output is correct
9 Correct 127 ms 7884 KB Output is correct
10 Correct 338 ms 20372 KB Output is correct
11 Correct 215 ms 21396 KB Output is correct
12 Correct 210 ms 19832 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 134 ms 13884 KB Output is correct
15 Correct 27 ms 2016 KB Output is correct
16 Correct 464 ms 20640 KB Output is correct
17 Correct 217 ms 20016 KB Output is correct
18 Correct 211 ms 20024 KB Output is correct
19 Correct 530 ms 69588 KB Output is correct
20 Correct 519 ms 67020 KB Output is correct
21 Correct 515 ms 69488 KB Output is correct
22 Correct 540 ms 66992 KB Output is correct
23 Correct 507 ms 67028 KB Output is correct
24 Correct 504 ms 67016 KB Output is correct
25 Correct 503 ms 66996 KB Output is correct
26 Correct 502 ms 69564 KB Output is correct
27 Correct 524 ms 69424 KB Output is correct
28 Correct 510 ms 66976 KB Output is correct
29 Correct 509 ms 66980 KB Output is correct
30 Correct 509 ms 66924 KB Output is correct