oj.uz

답안 #480153

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480153 2021-10-14T20:49:11 Z Apiram 벽 (IOI14_wall) C++14
100 / 100
 1696 ms 161980 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int64_t MXN = 2e6;
vector<int64_t>uptree(4*MXN);
vector<int64_t>downtree(4*MXN);
int64_t func(int64_t a,int64_t b){
return min(a,b);
}
void build(int64_t node,int64_t node_low,int64_t node_high){
	if (node_low==node_high){
		uptree[node]=0;
		downtree[node]=INT_MAX;
	}
	else {
		int64_t mid  =(node_low+node_high)>>1;
		build(node*2,node_low,mid);
		build(node*2 + 1,mid+1,node_high);
		uptree[node]=func(uptree[node*2],uptree[node*2 + 1]);	
		downtree[node]=func(downtree[node*2],downtree[node*2 + 1]);	
	}
}
void push(int64_t x){
 
            uptree[x + x] = max(uptree[x],uptree[x+x]);
            uptree[x + x + 1] = max(uptree[x],uptree[x+x + 1]);
            downtree[x + x] = min(downtree[x],downtree[x+x]);
            downtree[x + x + 1] = min(downtree[x],downtree[x+x+1]);
            uptree[x+x] = min(uptree[x+x],downtree[x]);
            uptree[x+x+1] = min(uptree[x+x+1],downtree[x]);
            downtree[x + x] = max(uptree[x],downtree[x+x]);
            downtree[x + x + 1] = max(uptree[x],downtree[x+x+1]);
            
        
}
void update(int64_t node,int64_t node_low,int64_t node_high,int64_t q_low,int64_t q_high,int64_t new_val,int ok){
	
	if (node_low>node_high||node_low>q_high||node_high<q_low)return;
	if (q_low<=node_low&&q_high>=node_high){
		if (ok==1){
			uptree[node] = max(uptree[node],new_val);
			downtree[node] = max(downtree[node],new_val);
		}
		else{
			uptree[node] = min(uptree[node],new_val);
			downtree[node] = min(downtree[node],new_val);
		}
		return ;
	}
	push(node);
	downtree[node]=INT_MAX, uptree[node]=0;
	int64_t mid = (node_low + node_high)/2;
	update(node*2,node_low,mid,q_low,q_high,new_val,ok);
	update(node*2  + 1,mid + 1,node_high,q_low,q_high,new_val,ok);
	//downtree[node]= func(downtree[node*2],downtree[node*2 + 1]); 
//	uptree[node]= func(uptree[node*2],uptree[node*2 + 1]); 
 
}
int64_t query(int64_t node,int64_t node_low,int64_t node_high,int64_t query_low,int64_t query_high){
	if (node_low>node_high||node_low>query_high||node_high<query_low)return INT_MAX;
	if (query_low<=node_low&&query_high>=node_high){
	return min(uptree[node],downtree[node]);
	}
	push(node);
	int64_t mid = (node_low+node_high)/2;
	return func(query(node*2,node_low,mid,query_low,query_high),query(node*2 + 1,mid+1,node_high,query_low,query_high));
}
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],height[i],op[i]);
  	}
  	for (int i = 0;i<n;++i){
  		finalHeight[i] = query(1,0,n-1,i,i);
  	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 125460 KB Output is correct
2 Correct 59 ms 125612 KB Output is correct
3 Correct 57 ms 125472 KB Output is correct
4 Correct 64 ms 125764 KB Output is correct
5 Correct 63 ms 125764 KB Output is correct
6 Correct 65 ms 125788 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 125448 KB Output is correct
2 Correct 209 ms 133296 KB Output is correct
3 Correct 242 ms 128840 KB Output is correct
4 Correct 631 ms 135244 KB Output is correct
5 Correct 433 ms 135752 KB Output is correct
6 Correct 426 ms 135840 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 125484 KB Output is correct
2 Correct 60 ms 125572 KB Output is correct
3 Correct 62 ms 125508 KB Output is correct
4 Correct 63 ms 125676 KB Output is correct
5 Correct 61 ms 125728 KB Output is correct
6 Correct 76 ms 125812 KB Output is correct
7 Correct 71 ms 125500 KB Output is correct
8 Correct 202 ms 134692 KB Output is correct
9 Correct 265 ms 130196 KB Output is correct
10 Correct 601 ms 135204 KB Output is correct
11 Correct 453 ms 135748 KB Output is correct
12 Correct 446 ms 135748 KB Output is correct
13 Correct 57 ms 125420 KB Output is correct
14 Correct 199 ms 134632 KB Output is correct
15 Correct 88 ms 126660 KB Output is correct
16 Correct 611 ms 135588 KB Output is correct
17 Correct 426 ms 135636 KB Output is correct
18 Correct 438 ms 135516 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 125508 KB Output is correct
2 Correct 57 ms 125568 KB Output is correct
3 Correct 61 ms 125560 KB Output is correct
4 Correct 64 ms 125684 KB Output is correct
5 Correct 72 ms 125764 KB Output is correct
6 Correct 61 ms 125704 KB Output is correct
7 Correct 56 ms 125448 KB Output is correct
8 Correct 197 ms 134684 KB Output is correct
9 Correct 248 ms 130192 KB Output is correct
10 Correct 593 ms 135324 KB Output is correct
11 Correct 445 ms 135748 KB Output is correct
12 Correct 427 ms 135840 KB Output is correct
13 Correct 57 ms 125508 KB Output is correct
14 Correct 214 ms 134740 KB Output is correct
15 Correct 95 ms 126624 KB Output is correct
16 Correct 629 ms 135500 KB Output is correct
17 Correct 427 ms 135568 KB Output is correct
18 Correct 429 ms 135596 KB Output is correct
19 Correct 1696 ms 151796 KB Output is correct
20 Correct 1683 ms 159404 KB Output is correct
21 Correct 1674 ms 161868 KB Output is correct
22 Correct 1630 ms 159624 KB Output is correct
23 Correct 1651 ms 159396 KB Output is correct
24 Correct 1649 ms 159428 KB Output is correct
25 Correct 1677 ms 159556 KB Output is correct
26 Correct 1682 ms 161972 KB Output is correct
27 Correct 1677 ms 161980 KB Output is correct
28 Correct 1645 ms 159540 KB Output is correct
29 Correct 1663 ms 159516 KB Output is correct
30 Correct 1647 ms 159612 KB Output is correct