oj.uz

Submission #164155

# Submission time Handle Problem Language Result Execution time Memory
164155 2019-11-17T18:56:22 Z kostia244 Wall (IOI14_wall) C++17
32 / 100
 1135 ms 28804 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 19 ms 504 KB Output is correct
5 Correct 18 ms 632 KB Output is correct
6 Correct 18 ms 632 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 167 ms 8184 KB Output is correct
3 Correct 352 ms 11864 KB Output is correct
4 Correct 1135 ms 28792 KB Output is correct
5 Correct 354 ms 28284 KB Output is correct
6 Correct 331 ms 28504 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 19 ms 504 KB Output is correct
5 Correct 19 ms 504 KB Output is correct
6 Correct 18 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 174 ms 8732 KB Output is correct
9 Correct 342 ms 12252 KB Output is correct
10 Correct 1065 ms 28708 KB Output is correct
11 Correct 359 ms 28360 KB Output is correct
12 Correct 333 ms 28508 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 174 ms 14044 KB Output is correct
15 Incorrect 40 ms 2808 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 19 ms 504 KB Output is correct
5 Correct 18 ms 596 KB Output is correct
6 Correct 18 ms 636 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 168 ms 8628 KB Output is correct
9 Correct 317 ms 12380 KB Output is correct
10 Correct 1073 ms 28804 KB Output is correct
11 Correct 357 ms 28388 KB Output is correct
12 Correct 333 ms 28540 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 175 ms 14040 KB Output is correct
15 Incorrect 40 ms 2680 KB Output isn't correct
16 Halted 0 ms 0 KB -