oj.uz

Submission #896059

# Submission time Handle Problem Language Result Execution time Memory
896059 2023-12-31T15:08:22 Z AgentPengin Wall (IOI14_wall) C++17
100 / 100
 498 ms 78416 KB 
/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include "wall.h"
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 2e6 + 5;

int res[MAXN];
pair<int,int> st[MAXN << 2];

void pull(int id) {
	st[id].fi = max(st[id << 1].fi,st[id << 1 | 1].fi);
	st[id].se = min(st[id << 1].se,st[id << 1 | 1].se);
}

void getnew(int id,int val) {
	st[id].fi = st[id].se = val;
}

void push(int id) {
	if (st[id].fi != st[id].se) return;
	getnew(id << 1,st[id].se);
	getnew(id << 1 | 1,st[id].se);
}

void updateMax(int u,int v,int height,int id,int l,int r) {
	if (v < l || u > r || st[id].se >= height) return;
	if (u <= l && r <= v && st[id].fi <= height) {
		getnew(id,height);
		return;
	}
	push(id);
	int mid = l + r >> 1;
	updateMax(u,v,height,id << 1,l,mid);
	updateMax(u,v,height,id << 1 | 1,mid + 1,r);
	pull(id);
}

void updateMin(int u,int v,int height,int id,int l,int r) {
	if (v < l || u > r || st[id].fi <= height) return;
	if (u <= l && r <= v && st[id].se >= height) {
		getnew(id,height);
		return;
	}
	push(id);
	int mid = l + r >> 1;
	updateMin(u,v,height,id << 1,l,mid);
	updateMin(u,v,height,id << 1 | 1,mid + 1,r);
	pull(id);
}

void build(int id,int l,int r) {
	if (l == r) {
		res[l] = st[id].se;
		return;
	}
	push(id);
	int mid = l + r >> 1;
	build(id << 1,l,mid);
	build(id << 1 | 1,mid + 1,r);
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]) {
	for (int i = 0;i < k;i++) {
		if (op[i] == 1) updateMax(left[i],right[i],height[i],1,0,n - 1);
		else updateMin(left[i],right[i],height[i],1,0,n - 1);
	}
	build(1,0,n - 1);
	for (int i = 0;i < n;i++) finalHeight[i] = res[i];
}

Compilation message

wall.cpp: In function 'void updateMax(int, int, int, int, int, int)':
wall.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int mid = l + r >> 1;
      |            ~~^~~
wall.cpp: In function 'void updateMin(int, int, int, int, int, int)':
wall.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid = l + r >> 1;
      |            ~~^~~
wall.cpp: In function 'void build(int, int, int)':
wall.cpp:76:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 5 ms 4780 KB Output is correct
5 Correct 4 ms 4952 KB Output is correct
6 Correct 5 ms 4956 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 102 ms 16036 KB Output is correct
3 Correct 56 ms 11856 KB Output is correct
4 Correct 138 ms 22328 KB Output is correct
5 Correct 139 ms 23376 KB Output is correct
6 Correct 155 ms 22012 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 102 ms 15896 KB Output is correct
9 Correct 53 ms 11856 KB Output is correct
10 Correct 141 ms 22456 KB Output is correct
11 Correct 136 ms 23388 KB Output is correct
12 Correct 154 ms 21840 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 105 ms 15956 KB Output is correct
15 Correct 18 ms 5724 KB Output is correct
16 Correct 291 ms 22612 KB Output is correct
17 Correct 203 ms 22156 KB Output is correct
18 Correct 214 ms 22168 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 5 ms 4736 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 4 ms 4956 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 102 ms 16120 KB Output is correct
9 Correct 53 ms 11856 KB Output is correct
10 Correct 132 ms 22352 KB Output is correct
11 Correct 140 ms 23556 KB Output is correct
12 Correct 148 ms 21960 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 106 ms 15992 KB Output is correct
15 Correct 18 ms 5768 KB Output is correct
16 Correct 290 ms 22612 KB Output is correct
17 Correct 197 ms 22096 KB Output is correct
18 Correct 229 ms 22308 KB Output is correct
19 Correct 454 ms 78040 KB Output is correct
20 Correct 498 ms 75664 KB Output is correct
21 Correct 491 ms 78212 KB Output is correct
22 Correct 485 ms 75876 KB Output is correct
23 Correct 446 ms 75856 KB Output is correct
24 Correct 446 ms 75860 KB Output is correct
25 Correct 480 ms 75956 KB Output is correct
26 Correct 451 ms 78416 KB Output is correct
27 Correct 459 ms 78220 KB Output is correct
28 Correct 445 ms 75588 KB Output is correct
29 Correct 442 ms 75860 KB Output is correct
30 Correct 445 ms 75952 KB Output is correct