oj.uz

Submission #212421

# Submission time Handle Problem Language Result Execution time Memory
212421 2020-03-22T22:54:50 Z Dan13llljws Wall (IOI14_wall) C++14
100 / 100
 1382 ms 102520 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define INF 0x3f3f3f3f
#define lc i << 1
#define rc i << 1 | 1
const int MM = 2e6 + 5;
struct node{int l, r, lz1, lz2;}seg[MM << 2];
void update_add(int i, int v){
	seg[i].lz1 = max(seg[i].lz1, v);
	seg[i].lz2 = max(seg[i].lz2, v);
}
void update_remove(int i, int v){
	seg[i].lz1 = min(seg[i].lz1, v);
	seg[i].lz2 = min(seg[i].lz2, v);
}
void push_down(int i){
	update_add(lc, seg[i].lz1);
	update_add(rc, seg[i].lz1);
	seg[i].lz1 = 0;
	update_remove(lc, seg[i].lz2);
	update_remove(rc, seg[i].lz2);
	seg[i].lz2 = INF;
}
void build(int i, int l, int r){
	seg[i].l = l, seg[i].r = r;
	if (l == r) return;
	seg[i].lz2 = INF;
	int mid = l + r >> 1;
	build(lc, l, mid), build(rc, mid + 1, r);
}
void add(int i, int l, int r, int v){
	if (seg[i].l == l && seg[i].r == r){
		update_add(i, v); return;
	}
	push_down(i);
	int mid = seg[i].l + seg[i].r >> 1;
	if (r <= mid) add(lc, l, r, v);
	else if (l > mid) add(rc, l, r, v);
	else add(lc, l, mid, v), add(rc, mid + 1, r, v);
}
void remove(int i, int l, int r, int v){
	if (seg[i].l == l && seg[i].r == r){
		update_remove(i, v); return;
	}
	push_down(i);
	int mid = seg[i].l + seg[i].r >> 1;
	if (r <= mid) remove(lc, l, r, v);
	else if (l > mid) remove(rc, l, r, v);
	else remove(lc, l, mid, v), remove(rc, mid + 1, r, v);
}
int query(int i, int pos){
	if (seg[i].l == pos && seg[i].r == pos) return seg[i].lz2;
	push_down(i);
	int mid = seg[i].l + seg[i].r >> 1;
	if (pos <= mid) return query(lc, pos);
	else return query(rc, pos);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	build(1, 1, n);
	for (int i = 0; i < k; i++){
		if (op[i] == 1) add(1, left[i] + 1, right[i] + 1, height[i]);
		else remove(1, left[i] + 1, right[i] + 1, height[i]);
	}
	for (int i = 0; i < n; i++) finalHeight[i] = query(1, i + 1);
}

Compilation message

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'void add(int, int, int, int)':
wall.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = seg[i].l + seg[i].r >> 1;
            ~~~~~~~~~^~~~~~~~~~
wall.cpp: In function 'void remove(int, int, int, int)':
wall.cpp:47:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = seg[i].l + seg[i].r >> 1;
            ~~~~~~~~~^~~~~~~~~~
wall.cpp: In function 'int query(int, int)':
wall.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = seg[i].l + seg[i].r >> 1;
            ~~~~~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 194 ms 13944 KB Output is correct
3 Correct 209 ms 8552 KB Output is correct
4 Correct 593 ms 22520 KB Output is correct
5 Correct 340 ms 23544 KB Output is correct
6 Correct 336 ms 22008 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 1152 KB Output is correct
5 Correct 12 ms 1152 KB Output is correct
6 Correct 12 ms 1152 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 192 ms 14000 KB Output is correct
9 Correct 199 ms 8572 KB Output is correct
10 Correct 563 ms 22520 KB Output is correct
11 Correct 346 ms 23544 KB Output is correct
12 Correct 341 ms 22008 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 198 ms 13992 KB Output is correct
15 Correct 39 ms 2552 KB Output is correct
16 Correct 581 ms 22756 KB Output is correct
17 Correct 369 ms 22136 KB Output is correct
18 Correct 338 ms 22252 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 1152 KB Output is correct
5 Correct 11 ms 1152 KB Output is correct
6 Correct 12 ms 1152 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 211 ms 13816 KB Output is correct
9 Correct 210 ms 8568 KB Output is correct
10 Correct 539 ms 22520 KB Output is correct
11 Correct 348 ms 23544 KB Output is correct
12 Correct 335 ms 22012 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 186 ms 13944 KB Output is correct
15 Correct 38 ms 2552 KB Output is correct
16 Correct 554 ms 22904 KB Output is correct
17 Correct 330 ms 22136 KB Output is correct
18 Correct 342 ms 22136 KB Output is correct
19 Correct 1305 ms 102520 KB Output is correct
20 Correct 1339 ms 99960 KB Output is correct
21 Correct 1329 ms 102444 KB Output is correct
22 Correct 1329 ms 99968 KB Output is correct
23 Correct 1299 ms 100100 KB Output is correct
24 Correct 1300 ms 100088 KB Output is correct
25 Correct 1346 ms 100152 KB Output is correct
26 Correct 1382 ms 102520 KB Output is correct
27 Correct 1331 ms 102372 KB Output is correct
28 Correct 1327 ms 99960 KB Output is correct
29 Correct 1358 ms 99956 KB Output is correct
30 Correct 1354 ms 100088 KB Output is correct