Submission #164155

#	Time	Username	Problem	Language	Result	Execution time	Memory
164155		kostia244	Wall (IOI14_wall)	C++17	32 / 100	1135 ms	28804 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]){
	if(n <= 10000) {
	for(int i = 0; i < k; i++) {
		if(op[i]==1) {
			for(int p = l[i]; p <= r[i]; p++)
				if(fh[p]<h[i]) fh[p] = h[i];
		} else {
			for(int p = l[i]; p <= r[i]; p++)
				if(fh[p]>h[i]) fh[p] = h[i];
		}
	}
	return;
	}
	vector<pair<int, int>> o[2][2];
	for(int i = 0; i < k; i++) {
		o[op[i]-1][0].pb({l[i], h[i]});
		o[op[i]-1][1].pb({r[i]+1, h[i]});
	}
	for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) sort(all(o[i][j]));
	int xa, xb, ya, yb;
	xa=xb=ya=yb=0;
	multiset<int, greater<int>> x;
	multiset<int> y;
	for(int i = 0; i < n; i++) {
		while(xa<o[0][0].size()&&o[0][0][xa].first==i) {
			x.insert(o[0][0][xa].second);
			xa++;
		}
		while(xb<o[0][1].size()&&o[0][1][xb].first==i) {
			x.erase(x.find(o[0][1][xb].second));
			xb++;
		}
		while(ya<o[1][0].size()&&o[1][0][ya].first==i) {
			y.insert(o[1][0][ya].second);
			ya++;
		}
		while(yb<o[1][1].size()&&o[1][1][yb].first==i) {
			y.erase(y.find(o[1][1][yb].second));
			yb++;
		}
		fh[i] = min(x.empty()?0:*x.begin(), y.empty()?INT_MAX:*y.begin());
	}
	return;
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:30:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(xa<o[0][0].size()&&o[0][0][xa].first==i) {
         ~~^~~~~~~~~~~~~~~
wall.cpp:34:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(xb<o[0][1].size()&&o[0][1][xb].first==i) {
         ~~^~~~~~~~~~~~~~~
wall.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ya<o[1][0].size()&&o[1][0][ya].first==i) {
         ~~^~~~~~~~~~~~~~~
wall.cpp:42:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(yb<o[1][1].size()&&o[1][1][yb].first==i) {
         ~~^~~~~~~~~~~~~~~

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