oj.uz

Submission #123409

# Submission time Handle Problem Language Result Execution time Memory
123409 2019-07-01T11:57:08 Z ekrem Wall (IOI14_wall) C++
100 / 100
 947 ms 69652 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas + son)/2)
#define sol (k+k)
#define sag (k+k+1)
#define inf 1000000007
#define N 2000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n;
ii seg[4*N];


void put(int k, int bas, int son, int op, int z){
	// cout << op << endl;
	// cout << "BAK" << bas << " " << son << " " << seg[k].st << " " << seg[k].nd << endl;
	if(op == 1){
		if(z >= seg[k].nd)
			seg[k] = mp(z, z);
		if(z >= seg[k].st)
			seg[k].st = z;
	}
	if(op == 0){
		if(z <= seg[k].st)
			seg[k] = mp(z, z);
		if(z <= seg[k].nd){
			seg[k].nd = z;
			// cout << z << " yaptim amk" << endl;
		}
	}
	// cout << "AMK" << bas << " " << son << " " << seg[k].st << " " << seg[k].nd << endl;
}

void push(int k, int bas, int son){
	if(seg[k].st != 0){
		put(sol, bas, orta, 1, seg[k].st);
		put(sag, orta + 1, son, 1, seg[k].st);
	}
	if(seg[k].nd != inf){
		put(sol, bas, orta, 0, seg[k].nd);
		put(sag, orta + 1, son, 0, seg[k].nd);
	}
	seg[k] = mp(0, inf);
}

void up(int k, int bas, int son, int x, int y, int op, int z){
	if(bas > y or son < x)
		return;
	if(bas >= x and son <= y){
		put(k, bas, son, op, z);
		return;
	}
	push(k, bas, son);
	up(sol, bas, orta, x, y, op, z);
	up(sag, orta + 1, son, x, y, op, z);
	// seg[k].st = min(seg[sol].st, seg[sag].st);
	// seg[k].nd = max(seg[sol].nd, seg[sag].nd);
}

int qu(int k, int bas, int son, int x){
	if(bas == son){
		// if(seg[k].st != seg[k].nd){
		// 	cout << "OF MAK " << seg[k].st << " " << seg[k].nd << endl;
		// }
		return seg[k].st;
	}
	push(k, bas, son);
	if(x <= orta)
		return qu(sol, bas, orta, x);
	else
		return qu(sag, orta + 1, son, x);
}

void bu(int k, int bas, int son){
	if(bas == son){
		seg[k] = mp(0, inf);
		return;
	}
	bu(sol, bas, orta);
	bu(sag, orta + 1, son);
	seg[k] = mp(0, inf);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	bu(1, 1, n);
	for(int i = 0; i < k; i++){
		// printf("%d %d %d %d\n", left[i] + 1, right[i] + 1, op[i], height[i] );
		up(1, 1, n, left[i] + 1, right[i] + 1, 2 - op[i], height[i]);
	}
	for(int i = 1; i <= n; i++)
		finalHeight[i - 1] = qu(1, 1, n, i);
	return;
}

// int main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// int n;
// int k;

// int i, j;  
// int status = 0;

// status = scanf("%d%d", &n, &k);
// assert(status == 2);

// int* op = (int*)calloc(sizeof(int), k);
// int* left = (int*)calloc(sizeof(int), k);
// int* right = (int*)calloc(sizeof(int), k);
// int* height = (int*)calloc(sizeof(int), k);
// int* finalHeight = (int*)calloc(sizeof(int), n);

// for (i = 0; i < k; i++){
// status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
// assert(status == 4);
// }

// buildWall(n, k, op, left, right, height, finalHeight);

// for (j = 0; j < n; j++)
// printf("%d\n", finalHeight[j]);

// return 0;
// }

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 504 KB Output is correct
3 Correct 4 ms 476 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 7 ms 888 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 181 ms 13944 KB Output is correct
3 Correct 225 ms 8120 KB Output is correct
4 Correct 671 ms 20452 KB Output is correct
5 Correct 315 ms 21640 KB Output is correct
6 Correct 308 ms 19976 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 8 ms 764 KB Output is correct
6 Correct 8 ms 892 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 175 ms 14200 KB Output is correct
9 Correct 230 ms 8024 KB Output is correct
10 Correct 669 ms 20344 KB Output is correct
11 Correct 315 ms 21624 KB Output is correct
12 Correct 306 ms 20080 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 179 ms 13944 KB Output is correct
15 Correct 44 ms 2168 KB Output is correct
16 Correct 764 ms 20728 KB Output is correct
17 Correct 313 ms 20204 KB Output is correct
18 Correct 316 ms 20080 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 8 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 174 ms 13932 KB Output is correct
9 Correct 226 ms 7928 KB Output is correct
10 Correct 729 ms 20472 KB Output is correct
11 Correct 316 ms 21496 KB Output is correct
12 Correct 306 ms 20008 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 179 ms 13944 KB Output is correct
15 Correct 46 ms 2040 KB Output is correct
16 Correct 770 ms 20688 KB Output is correct
17 Correct 312 ms 20088 KB Output is correct
18 Correct 320 ms 20064 KB Output is correct
19 Correct 937 ms 69576 KB Output is correct
20 Correct 937 ms 67064 KB Output is correct
21 Correct 947 ms 69652 KB Output is correct
22 Correct 935 ms 67040 KB Output is correct
23 Correct 930 ms 67160 KB Output is correct
24 Correct 925 ms 67192 KB Output is correct
25 Correct 945 ms 67252 KB Output is correct
26 Correct 937 ms 69604 KB Output is correct
27 Correct 946 ms 69624 KB Output is correct
28 Correct 932 ms 67088 KB Output is correct
29 Correct 931 ms 66964 KB Output is correct
30 Correct 930 ms 67192 KB Output is correct