oj.uz

Submission #159313

# Submission time Handle Problem Language Result Execution time Memory
159313 2019-10-22T09:47:43 Z TAISA_ Wall (IOI14_wall) C++14
32 / 100
 422 ms 20860 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct Segtree {
    int n;
    vector<int> s1, s2;
    Segtree(int n_) {
        n = 1;
        while (n < n_) {
            n <<= 1;
        }
        s1.resize(2 * n, 0);
        s2.resize(2 * n, 998244353);
    }
    void upd(int a, int b, P x, int t, int k, int l, int r) {
        if (b <= l || r <= a) {
            return;
        }
        if (a <= l && r <= b) {
            if (x.second == 1) {
                if (s1[k] < x.first) {
                    s1[k] = x.first;
                }
            } else {
                if (s2[k] > x.first) {
                    s2[k] = x.first;
                }
            }
            return;
        }
        upd(a, b, x, t, k << 1, l, (l + r) >> 1);
        upd(a, b, x, t, k << 1 | 1, (l + r) >> 1, r);
    }
    void upd(int a, int b, P x, int t) { upd(a, b, x, t, 1, 0, n); }
    pair<int, int> get(int k) {
        k += n;
        int r1 = s1[k], r2 = s2[k];
        k >>= 1;
        while (k > 0) {
            r1 = max(r1, s1[k]);
            r2 = min(r2, s2[k]);
            k >>= 1;
        }
        return make_pair(r1, r2);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {
    if (k <= 5000 && n <= 10000) {
        for (int i = 0; i < n; i++) {
            finalHeight[i] = 0;
        }
        for (int i = 0; i < k; i++) {
            for (int j = left[i]; j <= right[i]; j++) {
                if (op[i] == 1) {
                    finalHeight[j] = max(finalHeight[j], height[i]);
                } else {
                    finalHeight[j] = min(finalHeight[j], height[i]);
                }
            }
        }
    } else {
        Segtree seg(n);
        for (int i = 0; i < k; i++) {
            seg.upd(left[i], right[i] + 1, P(height[i], op[i]), i);
        }
        for (int i = 0; i < n; i++) {
            pair<int, int> p = seg.get(i);
            finalHeight[i] = min(p.first, p.second);
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 25 ms 504 KB Output is correct
5 Correct 25 ms 504 KB Output is correct
6 Correct 26 ms 504 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 172 ms 8208 KB Output is correct
3 Correct 157 ms 8000 KB Output is correct
4 Correct 422 ms 20284 KB Output is correct
5 Correct 264 ms 20860 KB Output is correct
6 Correct 253 ms 19272 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 25 ms 508 KB Output is correct
5 Correct 25 ms 504 KB Output is correct
6 Correct 26 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 172 ms 8188 KB Output is correct
9 Correct 152 ms 8092 KB Output is correct
10 Correct 421 ms 20148 KB Output is correct
11 Correct 268 ms 20856 KB Output is correct
12 Correct 253 ms 19240 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Incorrect 180 ms 13916 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 25 ms 472 KB Output is correct
5 Correct 25 ms 504 KB Output is correct
6 Correct 26 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 173 ms 8156 KB Output is correct
9 Correct 153 ms 7928 KB Output is correct
10 Correct 422 ms 20288 KB Output is correct
11 Correct 263 ms 20856 KB Output is correct
12 Correct 255 ms 19320 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Incorrect 181 ms 13944 KB Output isn't correct
15 Halted 0 ms 0 KB -