oj.uz

Submission #389948

# Submission time Handle Problem Language Result Execution time Memory
389948 2021-04-14T22:18:39 Z ritul_kr_singh Wall (IOI14_wall) C++17
100 / 100
 1032 ms 56804 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define sp << ' ' <<
#define nl << '\n'
#include "wall.h"
 
const int INF = 1e9;
 
struct SegmentTree{
	using T = array<int, 2>;
	vector<T> a;
	int sz = 1;
	T ID = {0, INF};
	SegmentTree(int n){
		while(sz < n) sz += sz;
		a.assign(2*sz, ID);
	}
	void apply(T &x, T &y){
		y[0] = max(y[0], x[0]);
		y[1] = max(y[1], x[0]);
		y[0] = min(y[0], x[1]);
		y[1] = min(y[1], x[1]);
	}
	void push(int x){
		if(a[x] == ID) return;
		if(x+1<sz){
			apply(a[x], a[2*x+1]);
			apply(a[x], a[2*x+2]);
			a[x] = ID;
		}
	}
	void update(int l, int r, T v, int x, int lx, int rx){
		push(x);
		if(r<=lx or rx<=l) return;
		if(l<=lx and rx<=r) return apply(v, a[x]);
		int mx = (lx+rx)/2;
		update(l, r, v, 2*x+1, lx, mx);
		update(l, r, v, 2*x+2, mx, rx);
	}
	void update(int l, int r, int low, int high){
		T v = {low, high};
		update(l, r+1, v, 0, 0, sz);
	}
	void build(vector<int> &ans, int n, int x, int lx, int rx){
		push(x);
		if(rx-lx==1){
			if(lx<n) ans[lx] = a[x][0];
			return;
		}
		int mx = (lx+rx)/2;
		build(ans, n, 2*x+1, lx, mx);
		build(ans, n, 2*x+2, mx, rx);
	}
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegmentTree st(n);
	for(int i=0; i<k; ++i){
		if(op[i]==1) st.update(left[i], right[i], height[i], INF);
		else st.update(left[i], right[i], 0, height[i]);
	}
	vector<int> ans(n);
 
	st.build(ans, n, 0, 0, st.sz);
	for(int i=0; i<n; ++i) finalHeight[i] = ans[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 676 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 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 169 ms 8276 KB Output is correct
3 Correct 255 ms 4108 KB Output is correct
4 Correct 781 ms 10952 KB Output is correct
5 Correct 372 ms 10948 KB Output is correct
6 Correct 372 ms 10904 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 680 KB Output is correct
5 Correct 6 ms 680 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 158 ms 8132 KB Output is correct
9 Correct 253 ms 4116 KB Output is correct
10 Correct 798 ms 10956 KB Output is correct
11 Correct 367 ms 10948 KB Output is correct
12 Correct 399 ms 10948 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 164 ms 8028 KB Output is correct
15 Correct 53 ms 1408 KB Output is correct
16 Correct 729 ms 10948 KB Output is correct
17 Correct 384 ms 10944 KB Output is correct
18 Correct 370 ms 10956 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 2 ms 332 KB Output is correct
4 Correct 8 ms 664 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 157 ms 8056 KB Output is correct
9 Correct 263 ms 4116 KB Output is correct
10 Correct 746 ms 10948 KB Output is correct
11 Correct 403 ms 10948 KB Output is correct
12 Correct 402 ms 10956 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 160 ms 8092 KB Output is correct
15 Correct 54 ms 1300 KB Output is correct
16 Correct 733 ms 11076 KB Output is correct
17 Correct 376 ms 10952 KB Output is correct
18 Correct 415 ms 10872 KB Output is correct
19 Correct 949 ms 56584 KB Output is correct
20 Correct 965 ms 56572 KB Output is correct
21 Correct 1032 ms 56608 KB Output is correct
22 Correct 983 ms 56608 KB Output is correct
23 Correct 946 ms 56584 KB Output is correct
24 Correct 951 ms 56616 KB Output is correct
25 Correct 929 ms 56516 KB Output is correct
26 Correct 950 ms 56588 KB Output is correct
27 Correct 948 ms 56580 KB Output is correct
28 Correct 962 ms 56584 KB Output is correct
29 Correct 946 ms 56804 KB Output is correct
30 Correct 993 ms 56604 KB Output is correct