oj.uz

Submission #428979

# Submission time Handle Problem Language Result Execution time Memory
428979 2021-06-15T16:05:51 Z MeGustaElArroz23 Wall (IOI14_wall) C++14
100 / 100
 2273 ms 149600 KB 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

///////

#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;

int INF=2000000000;

struct node{
    int l;
    int r;
    int left;
    int right;
    pii minmax;
};

pii combine(pii a, pii b){ // a antes que b
	pii res;	
    res.first=max(a.first,b.first);
    res.second=min(a.second,b.second);
    if (res.first>res.second){
		if(a.first<b.first) res.second=res.first;
		else res.first=res.second;
    }
//cerr << a.first << ' '<<a.second << ' '<<b.first<<' '<<b.second<<' '<<res.first<<' '<<res.second<<'\n';

	return res;
}

int counter=0;
vector<node> st(5000000);

void create_tree(int l, int r){
	int ac=counter;
	st[ac].l=l;
	st[ac].r=r;
	st[ac].minmax=pii{0,0};
	if (l!=r){
		//st[ac].minmax=pii{0,INF};
		counter++;
		st[ac].left=counter;
		create_tree(l,(l+r)/2);
		counter++;
		st[ac].right=counter;
		create_tree((l+r)/2+1,r);
	}
}

void push_tree(int ac, int l, int r, pii x){
	if (l==st[ac].l and r==st[ac].r){
		st[ac].minmax=combine(st[ac].minmax,x);
		return;
	}
	else{
		push_tree( st[ac].left , st[ac].l , (st[ac].l+st[ac].r)/2 , st[ac].minmax );
		push_tree( st[ac].right , (st[ac].l+st[ac].r)/2+1 , st[ac].r , st[ac].minmax );

		st[ac].minmax=pii{0,INF};

		int med=(st[ac].l+st[ac].r)/2;
		if (l>med){
			push_tree(st[ac].right , l , r , x);
		}
		else if (r<=med){
			push_tree(st[ac].left , l , r , x);
		}
		else{
			push_tree( st[ac].left , l , med , x );
			push_tree( st[ac].right, med+1 , r , x);
		}
		return;
	}
}

void buildWall(int n, int k, int type[], int left[], int right[], int height[], int finalHeight[]){
	create_tree(0,n-1);
	for (int i=0;i<k;i++){
		if (type[i]==1){
			push_tree(0,left[i],right[i],pii{height[i],INF});
		}
		else{
			push_tree(0,left[i],right[i],pii{0,height[i]});
		}
	//for (int x=0;x<n;x++){
	//	push_tree(0,x,x,pii{0,INF});
	//}
	
	//int x=0;
	//int j=0;
	//while (x<n){
	//	if (st[j].l==st[j].r){
	//		//cerr << st[j].l << ' '<<st[j].minmax.first<<'\n';
	//		x++;
	//	}
	//	j++;
	//}
	}
	
	for (int x=0;x<n;x++){
		push_tree(0,x,x,pii{0,INF});
	}
	int i=0;
	int j=0;
	while (i<n){
		if (st[j].l==st[j].r){
			finalHeight[st[j].l]=st[j].minmax.first;
			i++;
		}
		j++;
	}
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 117664 KB Output is correct
2 Correct 65 ms 117832 KB Output is correct
3 Correct 66 ms 117740 KB Output is correct
4 Correct 74 ms 117956 KB Output is correct
5 Correct 73 ms 117928 KB Output is correct
6 Correct 73 ms 117900 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 117660 KB Output is correct
2 Correct 222 ms 130048 KB Output is correct
3 Correct 335 ms 124756 KB Output is correct
4 Correct 809 ms 130048 KB Output is correct
5 Correct 573 ms 130132 KB Output is correct
6 Correct 607 ms 130828 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 117600 KB Output is correct
2 Correct 65 ms 117732 KB Output is correct
3 Correct 67 ms 117744 KB Output is correct
4 Correct 75 ms 117944 KB Output is correct
5 Correct 72 ms 117888 KB Output is correct
6 Correct 72 ms 117972 KB Output is correct
7 Correct 64 ms 117576 KB Output is correct
8 Correct 237 ms 130196 KB Output is correct
9 Correct 311 ms 124876 KB Output is correct
10 Correct 871 ms 129988 KB Output is correct
11 Correct 532 ms 130208 KB Output is correct
12 Correct 588 ms 130768 KB Output is correct
13 Correct 64 ms 117700 KB Output is correct
14 Correct 220 ms 130080 KB Output is correct
15 Correct 119 ms 118848 KB Output is correct
16 Correct 943 ms 130248 KB Output is correct
17 Correct 528 ms 130244 KB Output is correct
18 Correct 535 ms 130496 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 117700 KB Output is correct
2 Correct 76 ms 117776 KB Output is correct
3 Correct 68 ms 117652 KB Output is correct
4 Correct 74 ms 117884 KB Output is correct
5 Correct 74 ms 117880 KB Output is correct
6 Correct 76 ms 117940 KB Output is correct
7 Correct 64 ms 117700 KB Output is correct
8 Correct 215 ms 130104 KB Output is correct
9 Correct 333 ms 124920 KB Output is correct
10 Correct 824 ms 130008 KB Output is correct
11 Correct 542 ms 130096 KB Output is correct
12 Correct 561 ms 130944 KB Output is correct
13 Correct 65 ms 117576 KB Output is correct
14 Correct 241 ms 130036 KB Output is correct
15 Correct 116 ms 118888 KB Output is correct
16 Correct 961 ms 130344 KB Output is correct
17 Correct 580 ms 130524 KB Output is correct
18 Correct 541 ms 130512 KB Output is correct
19 Correct 2270 ms 147184 KB Output is correct
20 Correct 2273 ms 146720 KB Output is correct
21 Correct 2265 ms 149436 KB Output is correct
22 Correct 2179 ms 146792 KB Output is correct
23 Correct 2205 ms 146832 KB Output is correct
24 Correct 2205 ms 146748 KB Output is correct
25 Correct 2225 ms 146848 KB Output is correct
26 Correct 2235 ms 149600 KB Output is correct
27 Correct 2217 ms 149280 KB Output is correct
28 Correct 2158 ms 146844 KB Output is correct
29 Correct 2180 ms 146840 KB Output is correct
30 Correct 2187 ms 146872 KB Output is correct