oj.uz

Submission #221494

# Submission time Handle Problem Language Result Execution time Memory
221494 2020-04-10T10:17:37 Z staniewzki Wall (IOI14_wall) C++14
32 / 100
 3000 ms 9336 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
using namespace std;

#include "wall.h"

#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 = 900;
	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 4 ms 256 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 30 ms 508 KB Output is correct
5 Correct 28 ms 512 KB Output is correct
6 Correct 25 ms 504 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 181 ms 8160 KB Output is correct
3 Correct 587 ms 3696 KB Output is correct
4 Correct 1478 ms 8744 KB Output is correct
5 Correct 436 ms 9304 KB Output is correct
6 Correct 418 ms 9304 KB Output is correct

Subtask #3
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 37 ms 480 KB Output is correct
5 Correct 31 ms 512 KB Output is correct
6 Correct 27 ms 512 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 181 ms 8312 KB Output is correct
9 Correct 551 ms 3708 KB Output is correct
10 Correct 1476 ms 8956 KB Output is correct
11 Correct 421 ms 9212 KB Output is correct
12 Correct 405 ms 9208 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 195 ms 8164 KB Output is correct
15 Correct 170 ms 1016 KB Output is correct
16 Execution timed out 3080 ms 9080 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 30 ms 512 KB Output is correct
5 Correct 25 ms 504 KB Output is correct
6 Correct 25 ms 512 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 178 ms 8184 KB Output is correct
9 Correct 579 ms 3704 KB Output is correct
10 Correct 1458 ms 8824 KB Output is correct
11 Correct 442 ms 9336 KB Output is correct
12 Correct 407 ms 9208 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 185 ms 8184 KB Output is correct
15 Correct 170 ms 896 KB Output is correct
16 Execution timed out 3082 ms 8984 KB Time limit exceeded
17 Halted 0 ms 0 KB -