oj.uz

Submission #530781

# Submission time Handle Problem Language Result Execution time Memory
530781 2022-02-26T18:45:10 Z PoPularPlusPlus Wall (IOI14_wall) C++17
100 / 100
 697 ms 64992 KB 
#include <bits/stdc++.h>

using namespace std;

#include "wall.h"

struct item {
	int rem , fin;
};

struct Seg {
	int siz;
	vector<item> sum;
	
	item nutral = {INT_MAX , 0};
	
	item merge(item a , item b){
		item ans;
		ans.fin = max(a.fin , min(b.fin , a.rem));
		ans.rem = min(a.rem , b.rem);
		return ans;
	}
	
	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		sum.assign(siz * 2 , nutral);
	}
	
	vector<int> v;
	
	void set(int n , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < n)v.push_back(sum[x].fin);
			return;
		}
		sum[2 * x + 1] = merge(sum[x] , sum[2 * x + 1]);
		sum[2 * x + 2] = merge(sum[x] , sum[2 * x + 2]);
		sum[x] = nutral;
		int m = (lx + rx)/2;
		set(n , 2 * x + 1 , lx , m);
		set(n , 2 * x + 2  , m , rx);
	}
	
	vector<int> setall(int n){
		v.clear();
		set(n , 0 , 0 , siz);
		return v;
	}
	
	void range_set(int l, int r , int op , int h , int x , int lx , int rx){
		if(rx <= l || lx >= r){
			return;
		}
		if(lx >= l && rx <= r){
			if(op == 2){
				sum[x].fin = min(sum[x].fin , h);
				sum[x].rem = min(sum[x].rem , h);
			}
			else sum[x].fin = max(sum[x].fin , h);
			return;
		}
		sum[2 * x + 1] = merge(sum[x] , sum[2 * x + 1]);
		sum[2 * x + 2] = merge(sum[x] , sum[2 * x + 2]);
		sum[x] = nutral;
		int m = (lx + rx)/2;
		range_set(l , r , op , h , 2 * x + 1 , lx , m);
		range_set(l ,r , op , h , 2 * x + 2 , m, rx);
	}
	
	void range_set(int l , int r , int op , int h){
		range_set(l , r , op , h , 0 , 0 , siz);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int hei[], int finalHeight[]){
  Seg st;
  st.init(n);
  for(int i = 0; i < k; i++){
	  st.range_set(left[i] , right[i]+1 , op[i] , hei[i]);
  }
  vector<int> v = st.setall(n);
  for(int i = 0; i < n; i++)finalHeight[i] = v[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 5 ms 844 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 4 ms 844 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 150 ms 8532 KB Output is correct
3 Correct 182 ms 4592 KB Output is correct
4 Correct 365 ms 11768 KB Output is correct
5 Correct 264 ms 11836 KB Output is correct
6 Correct 280 ms 11856 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 816 KB Output is correct
5 Correct 4 ms 748 KB Output is correct
6 Correct 5 ms 844 KB Output is correct
7 Correct 1 ms 284 KB Output is correct
8 Correct 136 ms 8496 KB Output is correct
9 Correct 140 ms 4620 KB Output is correct
10 Correct 361 ms 11780 KB Output is correct
11 Correct 259 ms 11836 KB Output is correct
12 Correct 239 ms 11836 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 139 ms 8480 KB Output is correct
15 Correct 34 ms 1808 KB Output is correct
16 Correct 376 ms 11792 KB Output is correct
17 Correct 247 ms 11836 KB Output is correct
18 Correct 249 ms 11772 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 844 KB Output is correct
5 Correct 7 ms 820 KB Output is correct
6 Correct 5 ms 744 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 134 ms 8412 KB Output is correct
9 Correct 146 ms 4652 KB Output is correct
10 Correct 384 ms 11840 KB Output is correct
11 Correct 251 ms 11800 KB Output is correct
12 Correct 244 ms 11744 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 137 ms 8388 KB Output is correct
15 Correct 24 ms 1824 KB Output is correct
16 Correct 399 ms 11836 KB Output is correct
17 Correct 245 ms 11856 KB Output is correct
18 Correct 259 ms 11892 KB Output is correct
19 Correct 593 ms 64900 KB Output is correct
20 Correct 617 ms 64876 KB Output is correct
21 Correct 608 ms 64992 KB Output is correct
22 Correct 633 ms 64972 KB Output is correct
23 Correct 660 ms 64928 KB Output is correct
24 Correct 593 ms 64876 KB Output is correct
25 Correct 601 ms 64984 KB Output is correct
26 Correct 697 ms 64868 KB Output is correct
27 Correct 593 ms 64808 KB Output is correct
28 Correct 598 ms 64800 KB Output is correct
29 Correct 625 ms 64740 KB Output is correct
30 Correct 600 ms 64740 KB Output is correct