Submission #1026963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026963		socpite	Wall (IOI14_wall)	C++17	0 / 100	407 ms	107816 KiB

wall

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

const int maxn = 2e6+5;
const int mxval = 1e5;

struct phase{
	int ty, h, id;
	phase(int _ty, int _h, int _id): ty(_ty), h(_h), id(_id){};
};
vector<phase> vec[maxn];

set<int> mx[mxval + 5][2];

int st[4*mxval + 20][2];

void edit(int ty, int pos, int l = 0, int r = mxval, int id = 1){
	if(l == r)st[id][ty] = (mx[l][ty].empty() ? 0 : *mx[l][ty].rend());
	else {
		int mid = (l+r)>>1;
		if(pos <= mid)edit(ty, pos, l, mid, id<<1);
		else edit(ty, pos, mid+1, r, id<<1|1);
		st[id][ty] = max(st[id<<1][ty], st[id<<1|1][ty]);
	}
}

int query(int lmax = 1, int rmax = 0, int l = 0, int r = mxval, int id = 1){
	if(l == r)return l;
	else {
		int mid = (l+r)>>1;
		if(max(st[id<<1][1], lmax) > max(st[id<<1|1][0], rmax))return query(lmax, max(st[id<<1|1][0], rmax), l, mid, id<<1);
		else return query(max(st[id<<1][1], lmax), rmax, mid+1, r, id<<1|1);
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 0; i < k; i++){
		vec[left[i]].push_back(phase(op[i]-1, height[i], i+2));
		vec[right[i] + 1].push_back(phase(op[i]-1, height[i], i+2));
	}
	for(int i = 0; i < n; i++){
		for(auto v: vec[i]){
			if(mx[v.h][v.ty].find(v.id) != mx[v.h][v.ty].end())mx[v.h][v.ty].erase(v.id);
			else mx[v.h][v.ty].insert(v.id);
			edit(v.ty, v.h);
		}
		finalHeight[i] = query();
	}
}

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