oj.uz

답안 #230741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230741 2020-05-11T13:57:11 Z cfalas 벽 (IOI14_wall) C++14
100 / 100
 896 ms 100216 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define ADD 1
#define REMOVE 2
#define MID ((l+r)/2)
typedef pair<int, int> ii;

#define INF 9999999
int seg[10000000];
int ll[10000000];
int lr[10000000];
ii lp[10000000];
int ans[1000000];
#define F first
#define S second
int n;
int TIME;

#define maxi(a,v) a[v] = max(a[v], ll[ind]);
#define mini(a,v) a[v] = min(a[v], lr[ind]);

void update(int rl, int rr, int k, int x, int l=0, int r=n-1, int ind=1){
	//cout<<l<<" "<<r<<" "<<ind<<endl;
	if(rl<=l && r<=rr){
		if(k==1){
			ll[ind] = max(ll[ind], x);
			lr[ind] = max(lr[ind], x);
		}
		else{
			ll[ind] = min(ll[ind], x);
			lr[ind] = min(lr[ind], x);
		}
		ans[rl] = ll[ind];
		return;
	}
	else if(l>rr || rl>r) return;

	maxi(ll, 2*ind);
	maxi(lr, 2*ind);
	maxi(ll, 2*ind+1);
	maxi(lr, 2*ind+1);
	mini(ll, 2*ind);
	mini(lr, 2*ind);
	mini(ll, 2*ind+1);
	mini(lr, 2*ind+1);
	ll[ind] = 0;
	lr[ind] = INF;

	update(rl, rr, k, x, l, MID, ind*2);
	update(rl, rr, k, x, MID+1, r, ind*2+1);
}


void query(int l=0, int r=n-1, int ind=1){
	if(l==r){
		ans[l] = ll[ind];
	}
	else{
		maxi(ll, 2*ind);
		maxi(lr, 2*ind);
		maxi(ll, 2*ind+1);
		maxi(lr, 2*ind+1);
		mini(ll, 2*ind);
		mini(lr, 2*ind);
		mini(ll, 2*ind+1);
		mini(lr, 2*ind+1);
		ll[ind] = 0;
		lr[ind] = INF;

		query(l, MID, ind*2);
		query(MID+1, r, ind*2+1);
	}
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	n = N;
	for(int i=0;i<=5 * n;i++) lr[i] = INF;
	for(int i=0;i<k;i++){
		TIME++;
		//cout<<op[i]<<" "<<left[i]<<" "<<right[i]<<" "<<height[i]<<endl;
		update(left[i], right[i], op[i], height[i]);
		//for(int j=1;j<=30;j++){ if(ll[j]==0) cout<<"- "; else cout<<ll[j]<<" ";}
		//cout<<endl;
		//for(int j=1;j<=30;j++){ if(lr[j]==INF) cout<<"- "; else cout<<lr[j]<<" ";}
		//cout<<endl;
		//query();
		/*
		for(int j=1;j<=30;j++){ if(ll[j]==0) cout<<"- "; else cout<<ll[j]<<" ";}
		cout<<endl;
		for(int j=1;j<=30;j++){ if(lr[j]==INF) cout<<"- "; else cout<<lr[j]<<" ";}
		cout<<endl;
		*/
		//cout<<"CURR: ";
		//for(int i=0;i<N;i++) cout<<ans[i]<<" ";
		//cout<<"\n--------------------\n";
		//cout<<endl;
	}
	query();
	for(int i=0;i<N;i++) finalHeight[i] = ans[i];

}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 171 ms 8184 KB Output is correct
3 Correct 198 ms 4348 KB Output is correct
4 Correct 537 ms 21856 KB Output is correct
5 Correct 355 ms 22904 KB Output is correct
6 Correct 359 ms 21368 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 11 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 171 ms 8216 KB Output is correct
9 Correct 213 ms 4472 KB Output is correct
10 Correct 549 ms 21740 KB Output is correct
11 Correct 363 ms 23032 KB Output is correct
12 Correct 352 ms 21240 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 181 ms 14076 KB Output is correct
15 Correct 36 ms 2176 KB Output is correct
16 Correct 569 ms 21976 KB Output is correct
17 Correct 349 ms 21496 KB Output is correct
18 Correct 365 ms 21496 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 175 ms 8184 KB Output is correct
9 Correct 206 ms 4472 KB Output is correct
10 Correct 568 ms 21752 KB Output is correct
11 Correct 358 ms 22776 KB Output is correct
12 Correct 376 ms 21368 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 177 ms 13988 KB Output is correct
15 Correct 37 ms 2296 KB Output is correct
16 Correct 574 ms 22104 KB Output is correct
17 Correct 360 ms 21648 KB Output is correct
18 Correct 368 ms 21580 KB Output is correct
19 Correct 837 ms 100088 KB Output is correct
20 Correct 798 ms 97660 KB Output is correct
21 Correct 824 ms 100212 KB Output is correct
22 Correct 810 ms 97660 KB Output is correct
23 Correct 801 ms 97684 KB Output is correct
24 Correct 798 ms 97656 KB Output is correct
25 Correct 800 ms 97632 KB Output is correct
26 Correct 857 ms 100168 KB Output is correct
27 Correct 896 ms 100216 KB Output is correct
28 Correct 792 ms 97624 KB Output is correct
29 Correct 817 ms 97656 KB Output is correct
30 Correct 803 ms 97660 KB Output is correct