oj.uz

Submission #221492

# Submission time Handle Problem Language Result Execution time Memory
221492 2020-04-10T10:09:45 Z staniewzki Wall (IOI14_wall) C++14
61 / 100
 3000 ms 23928 KB 
#include "wall.h"

#include<bits/stdc++.h>
using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	int block_size = sqrt(n);
	int block_count = (n + block_size - 1) / block_size;
	vector<int> low(block_count), high(block_count, 1e5);

	auto update_block = [&](int q) {
		int l = block_size * q;
		int r = min(n, block_size * (q + 1));
		FOR(i, l, r - 1) {
			if(finalHeight[i] < low[q]) finalHeight[i] = low[q];
			if(finalHeight[i] > high[q]) finalHeight[i] = high[q];
		}
		low[q] = 0, high[q] = 1e5;
	};

	REP(i, k) {
		int left_block = left[i] / block_size;
		int right_block = right[i] / block_size;

		auto update_interval = [&](int l, int r) {
			FOR(j, l, r) {
				if(op[i] == 1 && finalHeight[j] < height[i]) finalHeight[j] = height[i];
				if(op[i] == 2 && finalHeight[j] > height[i]) finalHeight[j] = height[i];
			};
		};

		if(left_block == right_block) {
			update_block(left_block);
			update_interval(left[i], right[i]);
		}
		else {
			update_block(left_block);
			update_block(right_block);

			int next_block = block_size * (left_block + 1) - 1;
			update_interval(left[i], next_block);

			int prev_block = block_size * right_block;
			update_interval(prev_block, right[i]);
		}

		FOR(j, left_block + 1, right_block - 1) {
			if(op[i] == 1 && low[j] < height[i]) {
				low[j] = height[i];
				if(low[j] > high[j]) high[j] = low[j];
			}
			if(op[i] == 2 && high[j] > height[i]) {
				high[j] = height[i];
				if(low[j] > high[j]) low[j] = high[j];
			}
		}
	}

	REP(i, block_count) update_block(i);
}

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 504 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 10 ms 640 KB Output is correct
5 Correct 10 ms 640 KB Output is correct
6 Correct 10 ms 640 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 14072 KB Output is correct
3 Correct 224 ms 7416 KB Output is correct
4 Correct 916 ms 18420 KB Output is correct
5 Correct 490 ms 19480 KB Output is correct
6 Correct 456 ms 17784 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 10 ms 640 KB Output is correct
5 Correct 10 ms 640 KB Output is correct
6 Correct 10 ms 640 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 201 ms 13996 KB Output is correct
9 Correct 220 ms 7544 KB Output is correct
10 Correct 921 ms 18580 KB Output is correct
11 Correct 469 ms 19448 KB Output is correct
12 Correct 434 ms 17784 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 194 ms 13944 KB Output is correct
15 Correct 42 ms 1528 KB Output is correct
16 Correct 916 ms 18680 KB Output is correct
17 Correct 461 ms 18040 KB Output is correct
18 Correct 462 ms 18040 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 11 ms 640 KB Output is correct
5 Correct 10 ms 640 KB Output is correct
6 Correct 10 ms 640 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 189 ms 13992 KB Output is correct
9 Correct 224 ms 7544 KB Output is correct
10 Correct 933 ms 18380 KB Output is correct
11 Correct 442 ms 19448 KB Output is correct
12 Correct 445 ms 18040 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 191 ms 13944 KB Output is correct
15 Correct 53 ms 1656 KB Output is correct
16 Correct 915 ms 18748 KB Output is correct
17 Correct 463 ms 18168 KB Output is correct
18 Correct 480 ms 18040 KB Output is correct
19 Execution timed out 3085 ms 23928 KB Time limit exceeded
20 Halted 0 ms 0 KB -