oj.uz

답안 #289559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
289559 2020-09-02T18:11:18 Z cheetose 벽 (IOI14_wall) C++17
100 / 100
 1514 ms 83556 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int mntree[1<<22], mxtree[1<<22], lazy[1<<22];
void propagation(int node, int S, int E)
{
	if (lazy[node] != -1)
	{
		mntree[node] = mxtree[node] = lazy[node];
		if (S != E)
		{
			lazy[2 * node] = lazy[node];
			lazy[2 * node + 1] = lazy[node];
		}
		lazy[node] = -1;
	}
}
void upd(int node, int S, int E, int i, int j, int op, int val)
{
	propagation(node, S, E);
	if (i > E || j < S) return;
	if (j >= E && i <= S)
	{
		if((op==1 && mntree[node]>=val) || (op==2 && mxtree[node]<=val))return;
		if((op==1 && mxtree[node]<=val) || (op==2 && mntree[node]>=val)){
			lazy[node]=val;
			propagation(node,S,E);
			return;
		}
	}
	if(S==E)return;
	upd(2 * node, S, (S + E) / 2, i, j, op, val);
	upd(2 * node + 1, (S + E) / 2 + 1, E, i, j, op, val);
	mntree[node] = min(mntree[2 * node], mntree[2 * node + 1]);
	mxtree[node] = max(mxtree[2 * node], mxtree[2 * node + 1]);
}
int find(int node,int S,int E,int i,int j){
	propagation(node, S, E);
	if (i > E || j < S) return -1;
	if (j >= E && i <= S) return mxtree[node];
	return max(find(node * 2, S, (S + E) / 2, i, j), find(2 * node + 1, (S + E) / 2 + 1, E, i, j));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<k;i++){
		int o=op[i],l=left[i],r=right[i],x=height[i];
		upd(1,0,n-1,l,r,o,x);
	}
	for(int i=0;i<n;i++){
		finalHeight[i]=find(1,0,n-1,i,i);
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 14 ms 896 KB Output is correct
5 Correct 11 ms 900 KB Output is correct
6 Correct 11 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 234 ms 8184 KB Output is correct
3 Correct 215 ms 4472 KB Output is correct
4 Correct 639 ms 19832 KB Output is correct
5 Correct 418 ms 20124 KB Output is correct
6 Correct 398 ms 20580 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 12 ms 896 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 186 ms 8132 KB Output is correct
9 Correct 209 ms 4472 KB Output is correct
10 Correct 662 ms 19752 KB Output is correct
11 Correct 406 ms 20088 KB Output is correct
12 Correct 405 ms 20472 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 251 ms 14072 KB Output is correct
15 Correct 47 ms 2296 KB Output is correct
16 Correct 871 ms 20288 KB Output is correct
17 Correct 407 ms 20344 KB Output is correct
18 Correct 406 ms 20344 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 184 ms 8184 KB Output is correct
9 Correct 211 ms 4600 KB Output is correct
10 Correct 604 ms 19832 KB Output is correct
11 Correct 411 ms 20344 KB Output is correct
12 Correct 387 ms 20472 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 200 ms 13944 KB Output is correct
15 Correct 47 ms 2304 KB Output is correct
16 Correct 896 ms 20388 KB Output is correct
17 Correct 428 ms 20472 KB Output is correct
18 Correct 410 ms 20472 KB Output is correct
19 Correct 1449 ms 83556 KB Output is correct
20 Correct 1478 ms 78116 KB Output is correct
21 Correct 1457 ms 80684 KB Output is correct
22 Correct 1474 ms 78140 KB Output is correct
23 Correct 1514 ms 78108 KB Output is correct
24 Correct 1484 ms 78088 KB Output is correct
25 Correct 1467 ms 78220 KB Output is correct
26 Correct 1450 ms 80636 KB Output is correct
27 Correct 1454 ms 80764 KB Output is correct
28 Correct 1433 ms 78076 KB Output is correct
29 Correct 1450 ms 78072 KB Output is correct
30 Correct 1431 ms 78088 KB Output is correct