oj.uz

답안 #420193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
420193 2021-06-08T07:30:04 Z Bill_00 벽 (IOI14_wall) C++14
100 / 100
 990 ms 77336 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define N 2000002
#define INF INT_MAX
using namespace std;
int up[N*4],down[N*4],ans[N];
void build(int id,int l,int r){
	if(l==r){
		down[id]=INF;
		return;
	}
	int m=l+r>>1;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
}
void query(int id,int l,int r){
	if(l==r){
		ans[l]=min(up[id],down[id]);
		return;
	}
	if(l!=r){
		up[id*2]=max(up[id],up[id*2]);
		up[id*2]=min(up[id*2],down[id]);
		down[id*2]=min(down[id],down[id*2]);
		down[id*2]=max(down[id*2],up[id]);
		up[id*2+1]=max(up[id],up[id*2+1]);
		up[id*2+1]=min(up[id*2+1],down[id]);
		down[id*2+1]=min(down[id],down[id*2+1]);
		down[id*2+1]=max(down[id*2+1],up[id]);
		up[id]=0;
		down[id]=INF;
	}
	int m=l+r>>1;
	query(id*2,l,m);
	query(id*2+1,m+1,r);
}
void update(int id,int l,int r,int L,int R,int op,int H){
	// cout << l << ' ' << r << "\n";
	if(l!=r){
		up[id*2]=max(up[id],up[id*2]);
		up[id*2]=min(up[id*2],down[id]);
		down[id*2]=min(down[id],down[id*2]);
		down[id*2]=max(down[id*2],up[id]);
		up[id*2+1]=max(up[id],up[id*2+1]);
		up[id*2+1]=min(up[id*2+1],down[id]);
		down[id*2+1]=min(down[id],down[id*2+1]);
		down[id*2+1]=max(down[id*2+1],up[id]);
		up[id]=0;
		down[id]=INF;
	}
	if(r<L || R<l){
		return;
	}
	if(L<=l && r<=R){
		if(op==1){
			up[id]=max(up[id],H);
			down[id]=max(down[id],H);
		}
		if(op==2){
			up[id]=min(up[id],H);
			down[id]=min(down[id],H);
		}
		return;
	}
	int m=l+r>>1;
	update(id*2,l,m,L,R,op,H);
	update(id*2+1,m+1,r,L,R,op,H);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	build(1,0,n-1);
	for(int i=0;i<k;i++){
		update(1,0,n-1,left[i],right[i],op[i],height[i]);
	}
	query(1,0,n-1);
	for(int i=0;i<n;i++){
		finalHeight[i]=ans[i];
	}
}

Compilation message

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:12:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |  int m=l+r>>1;
      |        ~^~
wall.cpp: In function 'void query(int, int, int)':
wall.cpp:33:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  int m=l+r>>1;
      |        ~^~
wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:65:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  int m=l+r>>1;
      |        ~^~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 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 844 KB Output is correct
5 Correct 6 ms 764 KB Output is correct
6 Correct 6 ms 844 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 155 ms 8080 KB Output is correct
3 Correct 193 ms 4348 KB Output is correct
4 Correct 621 ms 20700 KB Output is correct
5 Correct 377 ms 21828 KB Output is correct
6 Correct 368 ms 20152 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 8 ms 844 KB Output is correct
5 Correct 6 ms 844 KB Output is correct
6 Correct 9 ms 828 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 162 ms 13912 KB Output is correct
9 Correct 201 ms 7972 KB Output is correct
10 Correct 542 ms 20784 KB Output is correct
11 Correct 370 ms 21828 KB Output is correct
12 Correct 409 ms 20192 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 154 ms 13892 KB Output is correct
15 Correct 31 ms 2008 KB Output is correct
16 Correct 556 ms 20932 KB Output is correct
17 Correct 357 ms 20420 KB Output is correct
18 Correct 368 ms 20376 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 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 6 ms 868 KB Output is correct
5 Correct 8 ms 844 KB Output is correct
6 Correct 8 ms 772 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 149 ms 13980 KB Output is correct
9 Correct 193 ms 8040 KB Output is correct
10 Correct 577 ms 20780 KB Output is correct
11 Correct 375 ms 21756 KB Output is correct
12 Correct 361 ms 20224 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 153 ms 13928 KB Output is correct
15 Correct 32 ms 1988 KB Output is correct
16 Correct 556 ms 20996 KB Output is correct
17 Correct 358 ms 20432 KB Output is correct
18 Correct 364 ms 20420 KB Output is correct
19 Correct 897 ms 77288 KB Output is correct
20 Correct 939 ms 74768 KB Output is correct
21 Correct 876 ms 77336 KB Output is correct
22 Correct 905 ms 74736 KB Output is correct
23 Correct 907 ms 74760 KB Output is correct
24 Correct 887 ms 74836 KB Output is correct
25 Correct 915 ms 74928 KB Output is correct
26 Correct 895 ms 77280 KB Output is correct
27 Correct 868 ms 77288 KB Output is correct
28 Correct 990 ms 74724 KB Output is correct
29 Correct 870 ms 74740 KB Output is correct
30 Correct 906 ms 74840 KB Output is correct