Submission #385363

#	Time	Username	Problem	Language	Result	Execution time	Memory
385363		alireza_kaviani	Wall (IOI14_wall)	C++11	100 / 100	1139 ms	140396 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

typedef pair<int, int> pii;

#define X			first
#define Y			second
#define lc			id << 1
#define rc			lc | 1

const int MAXN = 2e6 + 10;
const int MOD = 1e9 + 7;

int N , ans[MAXN] , mx[MAXN << 2] , mn[MAXN << 2];
pii lz[MAXN << 2];

void apply(int id , pii val){
	mx[id] = max(mx[id] , val.X); mx[id] = min(mx[id] , val.Y);
	mn[id] = max(mn[id] , val.X); mn[id] = min(mn[id] , val.Y);
	if(val.X >= lz[id].Y)	lz[id] = {val.X , val.X};
	else	lz[id].X = max(lz[id].X , val.X);
	lz[id].Y = min(lz[id].Y , val.Y);
}

void minimize(int ql , int qr , int x , int id = 1 , int l = 0 , int r = N){
	if(qr <= l || r <= ql)	return;
	if(ql <= l && r <= qr){
		apply(id , {0 , x});
		return;
	}
	apply(lc , lz[id]);
	apply(rc , lz[id]); lz[id] = {0 , MOD};
	int mid = l + r >> 1;
	minimize(ql , qr , x , lc , l , mid);
	minimize(ql , qr , x , rc , mid , r);
	mn[id] = min(mn[lc] , mn[rc]);
	mx[id] = max(mx[lc] , mx[rc]);
}

void maximize(int ql , int qr , int x , int id = 1 , int l = 0 , int r = N){
	if(qr <= l || r <= ql)	return;
	if(ql <= l && r <= qr){
		apply(id , {x , MOD});
		return;
	}
	apply(lc , lz[id]);
	apply(rc , lz[id]); lz[id] = {0 , MOD};
	int mid = l + r >> 1;
	maximize(ql , qr , x , lc , l , mid);
	maximize(ql , qr , x , rc , mid , r);
	mn[id] = min(mn[lc] , mn[rc]);
	mx[id] = max(mx[lc] , mx[rc]);
}

void solve(int id = 1 , int l = 0 , int r = N){
	if(r - l == 1){
//		cout << mx[id] << ' ' << mn[id] << endl;
		ans[l] = mx[id];
		return;
	}
	apply(lc , lz[id]);
	apply(rc , lz[id]);
	int mid = l + r >> 1;
	solve(lc , l , mid);
	solve(rc , mid , r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	fill(lz , lz + MAXN * 4 , pii(0 , MOD)); N = n;
	for(int i = 0 ; i < k ; i++){
		if(op[i] == 1){
			maximize(left[i] , right[i] + 1 , height[i]);
		}
		if(op[i] == 2){
			minimize(left[i] , right[i] + 1 , height[i]);
		}
	}
	solve();
	for(int i = 0 ; i < n ; i++)	finalHeight[i] = ans[i];
	return;
}

Compilation message (stderr)

wall.cpp: In function 'void minimize(int, int, int, int, int, int)':
wall.cpp:34:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |  int mid = l + r >> 1;
      |            ~~^~~
wall.cpp: In function 'void maximize(int, int, int, int, int, int)':
wall.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int mid = l + r >> 1;
      |            ~~^~~
wall.cpp: In function 'void solve(int, int, int)':
wall.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid = l + r >> 1;
      |            ~~^~~

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