Submission #379174

#	Time	Username	Problem	Language	Result	Execution time	Memory
379174		Mounir	Wall (IOI14_wall)	C++14	24 / 100	1334 ms	49340 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(s) (int)s.size()
using namespace std;

struct Req {
	int val, ind;

	bool operator < (const Req &autre) const {
		if (val != autre.val)
			return val < autre.val;
		return ind < autre.ind;
	}
};

struct IReq {
	int val, ind;

	bool operator < (const Req &autre) const {
		if (val != autre.val)
			return val > autre.val;
		return ind < autre.ind;
	}
};

struct Event {
	bool estDeb;
	int date, ind;

	bool operator < (const Event &autre) const {
		if (date != autre.date)
			return date < autre.date;
		if (estDeb != autre.estDeb)
			return estDeb;
		return ind < autre.ind;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	int nVals = n, nReqs = k;
	vector<Event> events;
	for (int iReq = 0; iReq < nReqs; ++iReq){
		events.pb({true, left[iReq], iReq});
		events.pb({false, right[iReq], iReq});
	}

	sort(all(events));
	set<Req> upperBound;
	set<Req> lowerBound;
	int pointeur = 0;

	for (int iVal = 0; iVal < nVals; ++iVal){
		while (pointeur < sz(events) && events[pointeur].date == iVal && events[pointeur].estDeb){
			int iReq = events[pointeur].ind;
			if (op[iReq] == 1)
				lowerBound.insert({height[iReq], iReq});
			else
				upperBound.insert({height[iReq], iReq});
			++pointeur;
		}

		if (sz(upperBound) == 0 && sz(lowerBound) == 0)
			finalHeight[iVal] = 0;
		else if (sz(upperBound) >= 1 && sz(lowerBound) >= 1){
			if (upperBound.begin()->ind < lowerBound.begin()->ind)
				finalHeight[iVal] = lowerBound.begin()->val;
			else
				finalHeight[iVal] = upperBound.begin()->val;
		}
		else if (sz(upperBound) >= 1)
			finalHeight[iVal] = 0;	
		else
			finalHeight[iVal] = lowerBound.begin()->val;

		while (pointeur < sz(events) && events[pointeur].date == iVal && !events[pointeur].estDeb){
			int iReq = events[pointeur].ind;
			if (op[iReq] == 1)
				lowerBound.erase({height[iReq], iReq});
			else
				upperBound.erase({height[iReq], iReq});
			++pointeur;
		}	
	}
	return;
}

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