oj.uz

Submission #447810

# Submission time Handle Problem Language Result Execution time Memory
447810 2021-07-27T14:58:37 Z hhhhaura Wall (IOI14_wall) C++14
100 / 100
 1158 ms 68036 KB 
#include "wall.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()

#define INF 1000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define lld long double
#define pii pair<int, int>
#define random mt19938 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
int n;
vector<int> mn, mx;
void init_(int _n) {
	n = _n;
	mn.assign(2 * n + 1, INF);
	mx.assign(2 * n + 1, -INF);
}
int get(int L, int R) {
	L++, R++;
	return (L + R) | (L != R);
}
void push(int L, int R) {
	int nd = get(L, R), mid = (L + R) / 2;
	int l = get(L, mid), r = get(mid + 1, R);
	mx[l] = max(mx[l], mx[nd]);
	mx[r] = max(mx[r], mx[nd]);
	
	mn[l] = max(mn[l], mx[nd]);
	mn[r] = max(mn[r], mx[nd]);
	
	mn[l] = min(mn[l], mn[nd]);
	mn[r] = min(mn[r], mn[nd]);
	
	mn[nd] = INF, mx[nd] = -INF;
}
void down(int L, int R) {
	int nd = get(L, R), mid = (L + R) / 2;
	if(L == R) return;
	push(L, R);
	down(L, mid);
	down(mid + 1, R);
}
void modify(int L, int R, int l, int r, int op, int x) {
	int nd = get(L, R), mid = (L + R) / 2;
	if(l > R || r < L) return;
	if(L != R) push(L, R);
	if(l <= L && r >= R) {
		if(op == 2) mn[nd] = min(mn[nd], x);
		else mx[nd] = max(mx[nd], x), mn[nd] = max(mn[nd], x);
	}		
	else {
		modify(L, mid, l, r, op, x);
		modify(mid + 1, R, l, r, op, x);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	init_(n);
	rep(i, 0, k - 1) modify(0, n - 1, left[i], right[i], op[i], height[i]);
	down(0, n - 1);
	rep(i, 0, n - 1) finalHeight[i] = min(max(0, mx[get(i, i)]), mn[get(i, i)]);
	return;
}

Compilation message

wall.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
wall.cpp: In function 'void down(int, int)':
wall.cpp:56:6: warning: unused variable 'nd' [-Wunused-variable]
   56 |  int nd = get(L, R), mid = (L + R) / 2;
      |      ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 588 KB Output is correct
5 Correct 6 ms 588 KB Output is correct
6 Correct 6 ms 696 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 159 ms 13892 KB Output is correct
3 Correct 247 ms 7760 KB Output is correct
4 Correct 732 ms 19836 KB Output is correct
5 Correct 407 ms 20896 KB Output is correct
6 Correct 398 ms 19396 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 6 ms 588 KB Output is correct
6 Correct 7 ms 656 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 162 ms 13932 KB Output is correct
9 Correct 249 ms 7740 KB Output is correct
10 Correct 756 ms 19848 KB Output is correct
11 Correct 405 ms 20936 KB Output is correct
12 Correct 391 ms 19396 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 169 ms 13936 KB Output is correct
15 Correct 41 ms 1764 KB Output is correct
16 Correct 729 ms 20124 KB Output is correct
17 Correct 394 ms 19524 KB Output is correct
18 Correct 403 ms 19556 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 7 ms 588 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 163 ms 13880 KB Output is correct
9 Correct 246 ms 7620 KB Output is correct
10 Correct 739 ms 19804 KB Output is correct
11 Correct 408 ms 20892 KB Output is correct
12 Correct 398 ms 19268 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 162 ms 13876 KB Output is correct
15 Correct 40 ms 1752 KB Output is correct
16 Correct 739 ms 20136 KB Output is correct
17 Correct 402 ms 19524 KB Output is correct
18 Correct 395 ms 19524 KB Output is correct
19 Correct 1112 ms 68036 KB Output is correct
20 Correct 1112 ms 65416 KB Output is correct
21 Correct 1119 ms 67984 KB Output is correct
22 Correct 1111 ms 65508 KB Output is correct
23 Correct 1131 ms 65620 KB Output is correct
24 Correct 1110 ms 65592 KB Output is correct
25 Correct 1132 ms 65496 KB Output is correct
26 Correct 1157 ms 67948 KB Output is correct
27 Correct 1158 ms 67988 KB Output is correct
28 Correct 1109 ms 65604 KB Output is correct
29 Correct 1114 ms 65508 KB Output is correct
30 Correct 1123 ms 65388 KB Output is correct