oj.uz

Submission #489625

# Submission time Handle Problem Language Result Execution time Memory
489625 2021-11-23T12:48:14 Z ssense Wall (IOI14_wall) C++14
100 / 100
 701 ms 229964 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<ll>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
class SegmentTree{
public:
	//DEFINITIONS
	int N, sz, lim;
	vector<pair<ll, ll>> lazy;
	//BUILDING
	SegmentTree(int n)
	{
		N = n;
		sz = 6*N;
		lazy.assign(6*N+1, {MXL, 0});
	}
	vint get(int k)
	{
		for(int i = 1; i <= N+k; i++)
		{
			push(i);
		}
		vint ans;
		for(int i = k+1; i < N+k+1; i++)
		{
			ans.pb(min(lazy[i].fr, lazy[i].sc));
		}
		return ans;
	}
	void push(int v)
	{
		lazy[2*v].fr = min(lazy[2*v].fr, lazy[v].fr);
		lazy[2*v].fr = max(lazy[2*v].fr, lazy[v].sc);
		lazy[2*v].sc = max(lazy[2*v].sc, lazy[v].sc);
		lazy[2*v].sc = min(lazy[2*v].sc, lazy[v].fr);
		lazy[2*v+1].fr = min(lazy[2*v+1].fr, lazy[v].fr);
		lazy[2*v+1].fr = max(lazy[2*v+1].fr, lazy[v].sc);
		lazy[2*v+1].sc = max(lazy[2*v+1].sc, lazy[v].sc);
		lazy[2*v+1].sc = min(lazy[2*v+1].sc, lazy[v].fr);
	}
	void update1(int v, int tl, int tr, int l, int r, ll addend)
	{
		if (l > r){return;}
		if (l == tl && tr == r)
		{
			lazy[v].fr = max(lazy[v].fr, addend);
			lazy[v].sc = max(lazy[v].sc, addend);
			return;
		}
		else
		{
			push(v);
			lazy[v].fr = MXL;
			lazy[v].sc = 0;
			int tm = (tl + tr) / 2;
			update1(v*2, tl, tm, l, min(r, tm), addend);
			update1(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
		}
	}
	void update2(int v, int tl, int tr, int l, int r, ll addend)
	{
		if (l > r){return;}
		if (l == tl && tr == r)
		{
			lazy[v].fr = min(lazy[v].fr, addend);
			lazy[v].sc = min(lazy[v].sc, addend);
			return;
		}
		else
		{
			push(v);
			lazy[v].fr = MXL;
			lazy[v].sc = 0;
			int tm = (tl + tr) / 2;
			update2(v*2, tl, tm, l, min(r, tm), addend);
			update2(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
		}
	}
};


void buildWall(int n, int k, int type[], int l[], int r[], int h[], int finalHeight[])
{
	SegmentTree st(n);
	int kk = 1;
	while(kk < n)
	{
		kk*=2;
	}
	for(int i = 0; i < k; i++)
	{
		if(type[i] == 1)
		{
			st.update1(1, 1, kk, l[i]+1, r[i]+1, h[i]);
		}
		else
		{
			st.update2(1, 1, kk, l[i]+1, r[i]+1, h[i]);
		}
	}
	kk--;
	vint ans = st.get(kk);
	for(int i = 0; i < n; i++)
	{
		finalHeight[i] = ans[i];
	}
}
/*
int32_t main(){
	startt
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
}
*/
/*
 7 3
 4 1 3 4 0 2 3
 
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
 
10 1
1 1 8 4
 */

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 1484 KB Output is correct
5 Correct 4 ms 1612 KB Output is correct
6 Correct 5 ms 1580 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 129 ms 8148 KB Output is correct
3 Correct 144 ms 5696 KB Output is correct
4 Correct 407 ms 18784 KB Output is correct
5 Correct 261 ms 18808 KB Output is correct
6 Correct 245 ms 18784 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 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 1484 KB Output is correct
5 Correct 4 ms 1612 KB Output is correct
6 Correct 4 ms 1560 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 140 ms 13904 KB Output is correct
9 Correct 140 ms 9468 KB Output is correct
10 Correct 386 ms 28392 KB Output is correct
11 Correct 310 ms 28860 KB Output is correct
12 Correct 248 ms 27372 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 133 ms 13892 KB Output is correct
15 Correct 23 ms 3364 KB Output is correct
16 Correct 372 ms 28388 KB Output is correct
17 Correct 261 ms 27752 KB Output is correct
18 Correct 251 ms 27820 KB Output is correct

Subtask #4
39.0 / 39.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 1 ms 332 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 4 ms 1612 KB Output is correct
6 Correct 5 ms 1612 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 127 ms 13832 KB Output is correct
9 Correct 154 ms 9444 KB Output is correct
10 Correct 370 ms 28296 KB Output is correct
11 Correct 259 ms 28856 KB Output is correct
12 Correct 249 ms 27292 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 135 ms 13816 KB Output is correct
15 Correct 24 ms 3348 KB Output is correct
16 Correct 391 ms 28476 KB Output is correct
17 Correct 258 ms 27836 KB Output is correct
18 Correct 247 ms 27740 KB Output is correct
19 Correct 687 ms 229964 KB Output is correct
20 Correct 664 ms 224692 KB Output is correct
21 Correct 662 ms 224680 KB Output is correct
22 Correct 669 ms 224644 KB Output is correct
23 Correct 671 ms 224716 KB Output is correct
24 Correct 701 ms 224652 KB Output is correct
25 Correct 653 ms 224636 KB Output is correct
26 Correct 666 ms 224652 KB Output is correct
27 Correct 663 ms 224652 KB Output is correct
28 Correct 683 ms 224632 KB Output is correct
29 Correct 669 ms 224764 KB Output is correct
30 Correct 662 ms 224672 KB Output is correct