Submission #896059

#	Time	Username	Problem	Language	Result	Execution time	Memory
896059		AgentPengin	Wall (IOI14_wall)	C++17	100 / 100	498 ms	78416 KiB

wall

/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include "wall.h"
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 2e6 + 5;

int res[MAXN];
pair<int,int> st[MAXN << 2];

void pull(int id) {
	st[id].fi = max(st[id << 1].fi,st[id << 1 | 1].fi);
	st[id].se = min(st[id << 1].se,st[id << 1 | 1].se);
}

void getnew(int id,int val) {
	st[id].fi = st[id].se = val;
}

void push(int id) {
	if (st[id].fi != st[id].se) return;
	getnew(id << 1,st[id].se);
	getnew(id << 1 | 1,st[id].se);
}

void updateMax(int u,int v,int height,int id,int l,int r) {
	if (v < l || u > r || st[id].se >= height) return;
	if (u <= l && r <= v && st[id].fi <= height) {
		getnew(id,height);
		return;
	}
	push(id);
	int mid = l + r >> 1;
	updateMax(u,v,height,id << 1,l,mid);
	updateMax(u,v,height,id << 1 | 1,mid + 1,r);
	pull(id);
}

void updateMin(int u,int v,int height,int id,int l,int r) {
	if (v < l || u > r || st[id].fi <= height) return;
	if (u <= l && r <= v && st[id].se >= height) {
		getnew(id,height);
		return;
	}
	push(id);
	int mid = l + r >> 1;
	updateMin(u,v,height,id << 1,l,mid);
	updateMin(u,v,height,id << 1 | 1,mid + 1,r);
	pull(id);
}

void build(int id,int l,int r) {
	if (l == r) {
		res[l] = st[id].se;
		return;
	}
	push(id);
	int mid = l + r >> 1;
	build(id << 1,l,mid);
	build(id << 1 | 1,mid + 1,r);
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]) {
	for (int i = 0;i < k;i++) {
		if (op[i] == 1) updateMax(left[i],right[i],height[i],1,0,n - 1);
		else updateMin(left[i],right[i],height[i],1,0,n - 1);
	}
	build(1,0,n - 1);
	for (int i = 0;i < n;i++) finalHeight[i] = res[i];
}

Compilation message (stderr)

wall.cpp: In function 'void updateMax(int, int, int, int, int, int)':
wall.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int mid = l + r >> 1;
      |            ~~^~~
wall.cpp: In function 'void updateMin(int, int, int, int, int, int)':
wall.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid = l + r >> 1;
      |            ~~^~~
wall.cpp: In function 'void build(int, int, int)':
wall.cpp:76:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |  int mid = l + r >> 1;
      |            ~~^~~

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