oj.uz

Submission #393835

# Submission time Handle Problem Language Result Execution time Memory
393835 2021-04-24T16:24:13 Z Mounir Wall (IOI14_wall) C++14
100 / 100
 1567 ms 69548 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(s) (int)s.size()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;
 
const int N = (1 << 21), OO = INT_MAX;
 
struct Noeud {
	int bornes[2];
};

Noeud arbre[N * 2];

void init(){
	for (int noeud = 1; noeud < 2 * N; ++noeud){
		arbre[noeud].bornes[0] = 0;
		arbre[noeud].bornes[1] = OO;
	}
}

void prop(int noeud){
	for (int enfant = noeud * 2; enfant <= noeud * 2 + 1; ++enfant){
		for (int iBorne = 0; iBorne < 2; ++iBorne){
			chmin(arbre[enfant].bornes[iBorne], arbre[noeud].bornes[1]);
			chmax(arbre[enfant].bornes[iBorne], arbre[noeud].bornes[0]);
		}
	}
}

void add(int noeud, int curl, int curr, int reql, int reqr, int typeReq, int val){
	if (curl > reqr || reql > curr)
		return;
	if (reql <= curl && curr <= reqr){
		for (int iBorne = 0; iBorne < 2; ++iBorne){
			if (typeReq == 2)
				chmin(arbre[noeud].bornes[iBorne], val);
			else
				chmax(arbre[noeud].bornes[iBorne], val);
		//	cout << "REQ " << arbre[noeud].bornes[0] << " " << arbre[noeud].bornes[1] << endl;
		}
		return;
	}

	int mid = (curl + curr)/2;
	prop(noeud);
	arbre[noeud].bornes[0] = 0; arbre[noeud].bornes[1] = OO;
	add(noeud * 2, curl, mid, reql, reqr, typeReq, val);
	add(noeud * 2 + 1, mid + 1, curr, reql, reqr, typeReq, val);
}

void toutPropager(int indice){
	add(1, 0, N - 1, indice, indice, 1, 0);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	init();

	int nVals = n, nReqs = k;
	for (int iReq = 0; iReq < nReqs; ++iReq){
		//left[iReq]++; right[iReq]++;
		add(1, 0, N - 1, left[iReq], right[iReq], op[iReq], height[iReq]);
		/*for (int iVal = 0; iVal < nVals; ++iVal){
			toutPropager(iVal);
			cout << arbre[N + iVal].bornes[0] << " ";
		}
		cout << endl;*/
	}

	for (int iVal = 0; iVal < nVals; ++iVal){
		toutPropager(iVal);
		finalHeight[iVal] = arbre[N + iVal].bornes[0];

		//cout << arbre[N + iVal].bornes[0] << " " << arbre[N + iVal].bornes[1] << endl;
	}
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 33100 KB Output is correct
2 Correct 23 ms 33096 KB Output is correct
3 Correct 20 ms 33100 KB Output is correct
4 Correct 29 ms 33284 KB Output is correct
5 Correct 34 ms 33292 KB Output is correct
6 Correct 28 ms 33256 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 33100 KB Output is correct
2 Correct 358 ms 40928 KB Output is correct
3 Correct 221 ms 36456 KB Output is correct
4 Correct 596 ms 51128 KB Output is correct
5 Correct 425 ms 52208 KB Output is correct
6 Correct 413 ms 50560 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33092 KB Output is correct
2 Correct 25 ms 33100 KB Output is correct
3 Correct 22 ms 33112 KB Output is correct
4 Correct 29 ms 33340 KB Output is correct
5 Correct 28 ms 33356 KB Output is correct
6 Correct 30 ms 33320 KB Output is correct
7 Correct 23 ms 33056 KB Output is correct
8 Correct 365 ms 46892 KB Output is correct
9 Correct 227 ms 40212 KB Output is correct
10 Correct 629 ms 51072 KB Output is correct
11 Correct 441 ms 52204 KB Output is correct
12 Correct 420 ms 50612 KB Output is correct
13 Correct 18 ms 33088 KB Output is correct
14 Correct 347 ms 46760 KB Output is correct
15 Correct 58 ms 34236 KB Output is correct
16 Correct 611 ms 51392 KB Output is correct
17 Correct 416 ms 50756 KB Output is correct
18 Correct 416 ms 50772 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33100 KB Output is correct
2 Correct 25 ms 33212 KB Output is correct
3 Correct 20 ms 33072 KB Output is correct
4 Correct 29 ms 33332 KB Output is correct
5 Correct 27 ms 33264 KB Output is correct
6 Correct 27 ms 33356 KB Output is correct
7 Correct 18 ms 33100 KB Output is correct
8 Correct 341 ms 46656 KB Output is correct
9 Correct 243 ms 40236 KB Output is correct
10 Correct 583 ms 51096 KB Output is correct
11 Correct 497 ms 52164 KB Output is correct
12 Correct 466 ms 50584 KB Output is correct
13 Correct 18 ms 33064 KB Output is correct
14 Correct 346 ms 46772 KB Output is correct
15 Correct 55 ms 34236 KB Output is correct
16 Correct 633 ms 51344 KB Output is correct
17 Correct 414 ms 50784 KB Output is correct
18 Correct 416 ms 50756 KB Output is correct
19 Correct 1497 ms 69508 KB Output is correct
20 Correct 1460 ms 67004 KB Output is correct
21 Correct 1449 ms 69512 KB Output is correct
22 Correct 1472 ms 66908 KB Output is correct
23 Correct 1434 ms 66904 KB Output is correct
24 Correct 1448 ms 66908 KB Output is correct
25 Correct 1500 ms 66944 KB Output is correct
26 Correct 1473 ms 69548 KB Output is correct
27 Correct 1467 ms 69452 KB Output is correct
28 Correct 1515 ms 66924 KB Output is correct
29 Correct 1540 ms 66920 KB Output is correct
30 Correct 1567 ms 66904 KB Output is correct