oj.uz

Submission #221495

# Submission time Handle Problem Language Result Execution time Memory
221495 2020-04-10T10:18:34 Z staniewzki Wall (IOI14_wall) C++14
32 / 100
 3000 ms 9464 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 = 1000;
	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 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 32 ms 504 KB Output is correct
5 Correct 28 ms 512 KB Output is correct
6 Correct 28 ms 512 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 182 ms 8132 KB Output is correct
3 Correct 605 ms 3704 KB Output is correct
4 Correct 1581 ms 8828 KB Output is correct
5 Correct 447 ms 9336 KB Output is correct
6 Correct 434 ms 9464 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 7 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 32 ms 504 KB Output is correct
5 Correct 28 ms 508 KB Output is correct
6 Correct 29 ms 504 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 189 ms 8184 KB Output is correct
9 Correct 627 ms 3704 KB Output is correct
10 Correct 1642 ms 8780 KB Output is correct
11 Correct 449 ms 9208 KB Output is correct
12 Correct 431 ms 9280 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 185 ms 8184 KB Output is correct
15 Correct 182 ms 896 KB Output is correct
16 Execution timed out 3071 ms 8652 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 39.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 32 ms 512 KB Output is correct
5 Correct 34 ms 512 KB Output is correct
6 Correct 29 ms 508 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 177 ms 8184 KB Output is correct
9 Correct 595 ms 3704 KB Output is correct
10 Correct 1539 ms 8824 KB Output is correct
11 Correct 447 ms 9336 KB Output is correct
12 Correct 443 ms 9304 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 188 ms 8376 KB Output is correct
15 Correct 181 ms 896 KB Output is correct
16 Execution timed out 3069 ms 8568 KB Time limit exceeded
17 Halted 0 ms 0 KB -