oj.uz

답안 #889017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
889017 2023-12-18T15:28:33 Z BBart888 벽 (IOI14_wall) C++14
0 / 100
 236 ms 82296 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN= 2e6+11;


int tmx[4*MAXN];
int tmn[4*MAXN];
pair<int,int> lazy[4*MAXN];

#define ff first
#define ss second


void pull_add(int x, int k){
    tmn[x] = max(tmn[x], k);
    tmx[x] = max(tmx[x], k);
    lazy[x].ff = max(lazy[x].ff, k);
    lazy[x].ss = max(lazy[x].ss, k);
}

void pull_dec(int x, int k){
    tmn[x] = min(tmn[x], k);
    tmx[x] = min(tmx[x], k);
    lazy[x].ff = min(lazy[x].ff, k);
    lazy[x].ss = min(lazy[x].ss, k);
}

void push(int x){
    if(lazy[x].ff != -1e9){
        pull_add(x << 1, lazy[x].ff);
        pull_add(x << 1 | 1, lazy[x].ff);
    }
    else if(lazy[x].ss != 1e9){
        pull_dec(x << 1, lazy[x].ss);
        pull_dec(x << 1 | 1, lazy[x].ss);
    }
    lazy[x] = {-1e9, 1e9};
}



void upd(int v,int tl,int  tr,int l,int r,int type,int val)
{
	if(l > r)
		return;
	if(l == tl && tr ==r)
	{
			if(type == 1)
				pull_add(v,val);
			else
				pull_dec(v,val);
			return;
	}
	int tm =(tl+tr)/2;
	push(v);
	upd(2*v,tl,tm,l,min(r,tm),type,val);
	upd(2*v+1,tm+1,tr,max(l,tm+1),r,type,val);
	tmx[v] = max(tmx[2*v],tmx[2*v+1]);
	tmn[v] = min(tmn[2*v],tmn[2*v+1]);
}


int get(int v,int tl,int tr,int pos)
{
	if(tl == tr)
		return tmx[v];
	int tm =(tl+tr)/2;
	push(v);
	if(pos <= tm)
		return get(2*v,tl,tm,pos);
	else
		return get(2*v+1,tm+1,tr,pos);
}



void buildWall(int n,int k,int op[],int left[],
int right[],int height[],int finalHeight[])
{
	for(int i = 0;i<4*MAXN;i++)
		lazy[i] = {-1e9,1e9};
	
	for(int i =0;i<k;i++)
		{
			if(op[i] == 1)
				upd(1,0,MAXN,left[i],right[i],1,height[i]);
			else
				upd(1,0,MAXN,left[i],right[i],0,height[i]);
		}

	for(int i =0;i<n;i++)
		finalHeight[i] = get(1,0,MAXN,i);
		
	

}
/*

int main()
{
	cin.tie(0);
	cout.tie(0);
	
	
	
	
	upd(1,0,MAXN,1,5,1,6);
	upd(1,0,MAXN,4,5,0,3);
	
	
	
	for(int i =0;i<=10;i++)
		cout<<get(1,0,MAXN,i)<<" ";
			

	
	
	
	
	
	return 0;
}

*/

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 74328 KB Output is correct
2 Correct 18 ms 74576 KB Output is correct
3 Incorrect 13 ms 70236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 74328 KB Output is correct
2 Correct 236 ms 82296 KB Output is correct
3 Incorrect 180 ms 73816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 74332 KB Output is correct
2 Correct 15 ms 74456 KB Output is correct
3 Incorrect 13 ms 70236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 74332 KB Output is correct
2 Correct 15 ms 74548 KB Output is correct
3 Incorrect 13 ms 70236 KB Output isn't correct
4 Halted 0 ms 0 KB -