oj.uz

답안 #293286

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
293286 2020-09-07T20:25:10 Z ant101 벽 (IOI14_wall) C++14
32 / 100
 3000 ms 19448 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 30 ms 580 KB Output is correct
5 Correct 24 ms 632 KB Output is correct
6 Correct 25 ms 640 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 183 ms 14072 KB Output is correct
3 Correct 601 ms 7544 KB Output is correct
4 Correct 1494 ms 18424 KB Output is correct
5 Correct 438 ms 19448 KB Output is correct
6 Correct 438 ms 17828 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 27 ms 640 KB Output is correct
5 Correct 24 ms 640 KB Output is correct
6 Correct 24 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 190 ms 14080 KB Output is correct
9 Correct 595 ms 7544 KB Output is correct
10 Correct 1521 ms 18424 KB Output is correct
11 Correct 423 ms 19448 KB Output is correct
12 Correct 415 ms 17784 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 186 ms 13944 KB Output is correct
15 Correct 176 ms 1528 KB Output is correct
16 Execution timed out 3071 ms 18168 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 27 ms 632 KB Output is correct
5 Correct 25 ms 632 KB Output is correct
6 Correct 24 ms 632 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 178 ms 13912 KB Output is correct
9 Correct 595 ms 7544 KB Output is correct
10 Correct 1526 ms 18452 KB Output is correct
11 Correct 469 ms 19396 KB Output is correct
12 Correct 441 ms 17784 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 185 ms 13944 KB Output is correct
15 Correct 177 ms 1528 KB Output is correct
16 Execution timed out 3038 ms 18168 KB Time limit exceeded
17 Halted 0 ms 0 KB -