Submission #423439

#	Time	Username	Problem	Language	Result	Execution time	Memory
423439		ismoilov	Wall (IOI14_wall)	C++14	0 / 100	11 ms	17612 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define maxx 2222222
#define inf 1e9

int mx[4*maxx], mn[4*maxx];
bool vis[maxx*4];

void maximize(int, int, int, int, int, int);
void minimize(int, int, int, int, int, int);

void max_self(int &a, int b){
	if(b > a)
		a = b;
}
void min_self(int &a, int b){
	if(b < a)
		a = b;
}
void minimize(int v, int l, int r, int tl, int tr, int h){
	if(tr < l || tl > r)
		return;
	if(tr >= r && tl <= l){
		min_self(mn[v], h);
		max_self(mx[v], mn[v]);
		vis[v] = 1;
		
		return;
	}
	
	int m = (l + r) >> 1;
	if(vis[v]){
		vis[v] = 0;
		vis[v+v] = vis[v+v+1] = 1;
		maximize(v+v, l, m, l, m, mx[v]);
		minimize(v+v, l, m, l, m, mn[v]);
		maximize(v+v+1, m+1, r, m+1, r, mx[v]);
		minimize(v+v+1, m+1, r, m+1, r, mn[v]);	
		mx[v] = 0;
		mn[v] = inf;
	}
	minimize(v+v, l, m, tl, tr, h);
	minimize(v+v+1, m+1, r, tl, tr, h);
}


void maximize(int v, int l, int r, int tl, int tr, int h){
	if(tr < l || tl > r)
		return;
	if(tl <= l && tr >= r){
		max_self(mx[v], h);
		max_self(mn[v], mx[v]);
		vis[v] = 1;
		return;
	}
	int m = (l + r) >> 1;
	if(vis[v]){
		vis[v] = 0;
		vis[v+v] = vis[v+v+1] = 1;
		maximize(v+v, l, m, l, m, mx[v]);
		minimize(v+v, l, m, l, m, mn[v]);
		maximize(v+v+1, m+1, r, m+1, r, mx[v]);
		minimize(v+v+1, m+1, r, m+1, r, mn[v]);	
		mx[v] = 0;
		mn[v] = inf;
	}
	maximize(v+v, l, m, tl, tr, h);
	maximize(v+v+1, m+1, r, tl, tr, h);
}


int get(int pos, int tl, int tr, int x){
	if(tl == tr)
		return mx[pos];
	int m = (tl+tr) >> 1;
	if(x <= m)
		return get(pos+pos, tl, m, x);
	else
		return get(pos+pos+1, m+1, tr, x);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	fp(i,0,maxx){
		mx[i] = 0;
		mn[i] = inf;
	}
	
	fp(i,0,k){
		if(op[i] == 1)
			maximize(1, 1, n, left[i]+1, right[i]+1, height[i]);
		else
			minimize(1, 1, n, left[i]+1, right[i]+1, height[i]);
	}
	
	fpp(i,1,n){
		minimize(1, 1, n, i, i, inf);
		finalHeight[i-1] = get(1, 1, n, i);
	}
	return;
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
wall.cpp:90:2: note: in expansion of macro 'fp'
   90 |  fp(i,0,maxx){
      |  ^~
wall.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
wall.cpp:95:2: note: in expansion of macro 'fp'
   95 |  fp(i,0,k){
      |  ^~
wall.cpp:8:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
wall.cpp:102:2: note: in expansion of macro 'fpp'
  102 |  fpp(i,1,n){
      |  ^~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39