oj.uz

Submission #253391

# Submission time Handle Problem Language Result Execution time Memory
253391 2020-07-27T21:29:39 Z ChrisT Wall (IOI14_wall) C++17
100 / 100
 757 ms 110268 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int MN = 2e6+5;
#define lc ind<<1
#define rc ind<<1|1
struct Node {
	int l,r,mx,mn;
} tree[MN<<2];
int ans[MN];
int le[MN], ri[MN], o[MN], he[MN], f[MN];
void build (int ind, int l, int r) {
	tree[ind] = {l,r,0,INT_MAX};
	if (l == r) return;
	int mid = (l+r)>>1;
	build(lc,l,mid), build(rc,mid+1,r);
}
void remove (int ind, int v) {
    tree[ind].mn = min(tree[ind].mn,v);
    tree[ind].mx = min(tree[ind].mx,v);
}
void add (int ind, int v) {
    tree[ind].mx = max(tree[ind].mx,v);
    tree[ind].mn = max(tree[ind].mn,v);
}
void push_down (int ind) {
    if (tree[ind].l == tree[ind].r) return;
    add(lc,tree[ind].mx);
    remove(lc,tree[ind].mn);
    add(rc,tree[ind].mx);
    remove(rc,tree[ind].mn);
    tree[ind].mx = 0, tree[ind].mn = INT_MAX;
}
void update (int ind, int l, int r, bool op, int v) {
    if (tree[ind].l > r || tree[ind].r < l) return;
    if (tree[ind].l >= l && tree[ind].r <= r) {
   	 op ? remove(ind,v) : add(ind,v);
   	 return;
    }
    push_down(ind);
    update(lc,l,r,op,v);
    update(rc,l,r,op,v);
}
void finish (int ind) {
    if (tree[ind].l == tree[ind].r) {
        ans[tree[ind].l] = min(tree[ind].mn,tree[ind].mx);
        return;
    }
    push_down(ind);
    finish (lc); finish (rc);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    build(1,0,n-1);
    for (int i = 0; i < k; i++) {
   	 update(1,left[i],right[i],op[i] == 2,height[i]);
    }
    finish(1);
    for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 180 ms 13944 KB Output is correct
3 Correct 189 ms 8568 KB Output is correct
4 Correct 519 ms 22904 KB Output is correct
5 Correct 329 ms 23928 KB Output is correct
6 Correct 314 ms 22392 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 180 ms 13944 KB Output is correct
9 Correct 188 ms 8696 KB Output is correct
10 Correct 549 ms 22904 KB Output is correct
11 Correct 348 ms 23928 KB Output is correct
12 Correct 330 ms 22392 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 185 ms 14072 KB Output is correct
15 Correct 31 ms 2684 KB Output is correct
16 Correct 528 ms 23124 KB Output is correct
17 Correct 327 ms 22520 KB Output is correct
18 Correct 338 ms 22520 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 188 ms 14072 KB Output is correct
9 Correct 187 ms 8568 KB Output is correct
10 Correct 549 ms 22908 KB Output is correct
11 Correct 327 ms 23928 KB Output is correct
12 Correct 323 ms 22520 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 190 ms 14004 KB Output is correct
15 Correct 31 ms 2680 KB Output is correct
16 Correct 520 ms 23160 KB Output is correct
17 Correct 324 ms 22748 KB Output is correct
18 Correct 326 ms 22520 KB Output is correct
19 Correct 722 ms 110268 KB Output is correct
20 Correct 724 ms 107768 KB Output is correct
21 Correct 735 ms 110256 KB Output is correct
22 Correct 736 ms 107744 KB Output is correct
23 Correct 724 ms 107784 KB Output is correct
24 Correct 729 ms 107768 KB Output is correct
25 Correct 719 ms 107768 KB Output is correct
26 Correct 757 ms 110240 KB Output is correct
27 Correct 745 ms 110192 KB Output is correct
28 Correct 715 ms 107768 KB Output is correct
29 Correct 722 ms 107744 KB Output is correct
30 Correct 718 ms 107788 KB Output is correct