oj.uz

Submission #492996

# Submission time Handle Problem Language Result Execution time Memory
492996 2021-12-10T00:48:08 Z peti1234 Wall (IOI14_wall) C++17
100 / 100
 666 ms 99736 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int c=1<<22, sok=1e9;
int kezd[c], veg[c], kis[c], nagy[c];
int s(int a, int l, int r) {
    if (r<kezd[a] || l>veg[a]) return 0;
    if (l<=kezd[a] && veg[a]<=r) return 2;
    return 1;
}
void push(int a) {
    int x=2*a, y=2*a+1;
    kis[x]=min(nagy[a], max(kis[x], kis[a]));
    nagy[x]=max(kis[a], min(nagy[x], nagy[a]));
    kis[y]=min(nagy[a], max(kis[y], kis[a]));
    nagy[y]=max(kis[a], min(nagy[y], nagy[a]));
    kis[a]=0, nagy[a]=sok;
}
void add(int a, int l, int r, int ert, int f) {
    int p=s(a, l, r);
    if (!p) return;
    if (p==2) {
        if (f==1) {
            kis[a]=max(kis[a], ert);
            nagy[a]=max(nagy[a], ert);
        } else {
            kis[a]=min(kis[a], ert);
            nagy[a]=min(nagy[a], ert);
        }
        return;
    }
    push(a);
    add(2*a, l, r, ert, f), add(2*a+1, l, r, ert, f);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
    int po=1;
    while (po<=n) po*=2;
    for (int i=po; i<2*po; i++) {
        kezd[i]=veg[i]=i-po;
        nagy[i]=sok;
    }
    for (int i=po-1; i>=1; i--) {
        kezd[i]=kezd[2*i], veg[i]=veg[2*i+1];
        nagy[i]=sok;
    }
    for (int i=0; i<k; i++) {
        add(1, l[i], r[i], h[i], op[i]);
    }
    for (int i=1; i<po; i++) {
        push(i);
    }
    for (int i=po; i<po+n; i++) {
        ans[i-po]=kis[i];
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 972 KB Output is correct
5 Correct 4 ms 972 KB Output is correct
6 Correct 6 ms 972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 141 ms 8048 KB Output is correct
3 Correct 152 ms 4732 KB Output is correct
4 Correct 413 ms 12860 KB Output is correct
5 Correct 269 ms 13324 KB Output is correct
6 Correct 314 ms 13324 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 5 ms 972 KB Output is correct
5 Correct 4 ms 972 KB Output is correct
6 Correct 5 ms 928 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 150 ms 8092 KB Output is correct
9 Correct 156 ms 4728 KB Output is correct
10 Correct 452 ms 12820 KB Output is correct
11 Correct 277 ms 13328 KB Output is correct
12 Correct 251 ms 13328 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 143 ms 8112 KB Output is correct
15 Correct 24 ms 1872 KB Output is correct
16 Correct 428 ms 13168 KB Output is correct
17 Correct 271 ms 12996 KB Output is correct
18 Correct 247 ms 13084 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 4 ms 972 KB Output is correct
6 Correct 7 ms 972 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 147 ms 8088 KB Output is correct
9 Correct 149 ms 4812 KB Output is correct
10 Correct 423 ms 12828 KB Output is correct
11 Correct 253 ms 13332 KB Output is correct
12 Correct 251 ms 13324 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 145 ms 8112 KB Output is correct
15 Correct 23 ms 1988 KB Output is correct
16 Correct 453 ms 13068 KB Output is correct
17 Correct 259 ms 13072 KB Output is correct
18 Correct 247 ms 13184 KB Output is correct
19 Correct 631 ms 91828 KB Output is correct
20 Correct 666 ms 97224 KB Output is correct
21 Correct 627 ms 99736 KB Output is correct
22 Correct 630 ms 97076 KB Output is correct
23 Correct 634 ms 97096 KB Output is correct
24 Correct 645 ms 97180 KB Output is correct
25 Correct 659 ms 97128 KB Output is correct
26 Correct 633 ms 99452 KB Output is correct
27 Correct 646 ms 99508 KB Output is correct
28 Correct 627 ms 96836 KB Output is correct
29 Correct 626 ms 96624 KB Output is correct
30 Correct 656 ms 97000 KB Output is correct