oj.uz

Submission #798158

# Submission time Handle Problem Language Result Execution time Memory
798158 2023-07-30T12:15:10 Z QwertyPi Wall (IOI14_wall) C++14
100 / 100
 605 ms 39956 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;
const int INF = 1 << 30;

struct range{
	int l, r;
	range operator+ (const range& o) const {
		if(r < o.l) return {o.l, o.l};
		if(l > o.r) return {o.r, o.r};
		return {max(o.l, l), min(o.r, r)};
	}
};

range t[1 << 21];
int k;
void build(int v = 0, int l = 0, int r = k - 1){
	if(l == r) return void(t[v] = {0, INF});
	int m = (l + r) / 2;
	build(v * 2 + 1, l, m); build(v * 2 + 2, m + 1, r);
	t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}

void update(int p, int op, int h, int v = 0, int l = 0, int r = k - 1){
	if(l == r){
		if(op == 0) t[v] = {0, INF};
		else if(op == 1) t[v] = {h, INF};
		else t[v] = {0, h};
		return;
	}
	int m = (l + r) / 2;
	if(p <= m) update(p, op, h, v * 2 + 1, l, m);
	else update(p, op, h, v * 2 + 2, m + 1, r);
	t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}

struct query{
	int t, p, op, h;
	bool operator< (const query& o) const {
		return t < o.t;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	::k = k;
	vector<query> Q;
	for(int i = 0; i < k; i++){
		Q.push_back({left[i], i, op[i], height[i]});
		Q.push_back({right[i] + 1, i, 0, height[i]});
	}
	build();
	sort(Q.begin(), Q.end());
	int qi = 0;
	for(int i = 0; i < n; i++){
		while(qi < Q.size() && Q[qi].t <= i) update(Q[qi].p, Q[qi].op, Q[qi].h), qi++;
		finalHeight[i] = t[0].l;
	}
	return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:56:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   while(qi < Q.size() && Q[qi].t <= i) update(Q[qi].p, Q[qi].op, Q[qi].h), qi++;
      |         ~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 4 ms 728 KB Output is correct
5 Correct 4 ms 728 KB Output is correct
6 Correct 4 ms 808 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 242 ms 32152 KB Output is correct
3 Correct 161 ms 14344 KB Output is correct
4 Correct 445 ms 32432 KB Output is correct
5 Correct 309 ms 32404 KB Output is correct
6 Correct 316 ms 32460 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 764 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 728 KB Output is correct
5 Correct 4 ms 796 KB Output is correct
6 Correct 5 ms 728 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 202 ms 32060 KB Output is correct
9 Correct 175 ms 14424 KB Output is correct
10 Correct 452 ms 32424 KB Output is correct
11 Correct 315 ms 32460 KB Output is correct
12 Correct 380 ms 32464 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 213 ms 32072 KB Output is correct
15 Correct 24 ms 2480 KB Output is correct
16 Correct 605 ms 32528 KB Output is correct
17 Correct 347 ms 32464 KB Output is correct
18 Correct 389 ms 32456 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 728 KB Output is correct
5 Correct 4 ms 728 KB Output is correct
6 Correct 4 ms 728 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 206 ms 32040 KB Output is correct
9 Correct 165 ms 14348 KB Output is correct
10 Correct 519 ms 32516 KB Output is correct
11 Correct 327 ms 32460 KB Output is correct
12 Correct 335 ms 32468 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 227 ms 32080 KB Output is correct
15 Correct 25 ms 2440 KB Output is correct
16 Correct 480 ms 32612 KB Output is correct
17 Correct 335 ms 32460 KB Output is correct
18 Correct 365 ms 32496 KB Output is correct
19 Correct 493 ms 39956 KB Output is correct
20 Correct 461 ms 39872 KB Output is correct
21 Correct 455 ms 39908 KB Output is correct
22 Correct 459 ms 39956 KB Output is correct
23 Correct 467 ms 39856 KB Output is correct
24 Correct 455 ms 39864 KB Output is correct
25 Correct 443 ms 39944 KB Output is correct
26 Correct 448 ms 39884 KB Output is correct
27 Correct 459 ms 39896 KB Output is correct
28 Correct 478 ms 39952 KB Output is correct
29 Correct 464 ms 39872 KB Output is correct
30 Correct 447 ms 39948 KB Output is correct