oj.uz

Submission #385431

# Submission time Handle Problem Language Result Execution time Memory
385431 2021-04-04T08:54:18 Z Keshi Wall (IOI14_wall) C++17
100 / 100
 793 ms 97388 KB 
//In the name of God
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e6 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)

pll seg[maxn << 2];
ll ans[maxn];

pll Do(pll f, pll s){
	if(f.S < s.F) return Mp(s.F, s.F);
	if(f.F > s.S) return Mp(s.S, s.S);
	return Mp(max(f.F, s.F), min(f.S, s.S));
}
void shift(ll id){
	seg[lc] = Do(seg[lc], seg[id]);
	seg[rc] = Do(seg[rc], seg[id]);
	seg[id] = Mp(0, inf);
	return;
}

void upd(ll id, ll s, ll e, ll l, ll r, pll x){
	if(r <= s || e <= l) return;
	if(l <= s && e <= r){
		seg[id] = Do(seg[id], x);
		return;
	}
	ll mid = (s + e) >> 1;
	shift(id);
	upd(lc, s, mid, l, r, x);
	upd(rc, mid, e, l, r, x);
	return;
}
void fix(ll id, ll s, ll e){
	if(e - s == 1){
		ans[s] = seg[id].F;
		return;
	}
	ll mid = (s + e) >> 1;
	shift(id);
	fix(lc, s, mid);
	fix(rc, mid, e);
	return;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	fill(seg, seg + (n << 2), Mp(0, inf));
	for(ll i = 0; i < k; i++){
		if(op[i] == 1){
			upd(1, 0, n, left[i], right[i] + 1, Mp(height[i], inf));
		}
		else{
			upd(1, 0, n, left[i], right[i] + 1, Mp(0, height[i]));
		}
	}
	fix(1, 0, n);
	for(ll i = 0; i < n; i++){
		finalHeight[i] = ans[i];
	}
	return;
}


/*int main(){
    fast_io;



    return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 7 ms 1004 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 155 ms 9000 KB Output is correct
3 Correct 160 ms 5228 KB Output is correct
4 Correct 475 ms 12908 KB Output is correct
5 Correct 301 ms 13520 KB Output is correct
6 Correct 290 ms 13420 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 9 ms 1004 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 157 ms 8940 KB Output is correct
9 Correct 185 ms 5196 KB Output is correct
10 Correct 557 ms 12908 KB Output is correct
11 Correct 310 ms 13420 KB Output is correct
12 Correct 287 ms 13420 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 163 ms 8940 KB Output is correct
15 Correct 35 ms 1900 KB Output is correct
16 Correct 593 ms 13156 KB Output is correct
17 Correct 303 ms 13248 KB Output is correct
18 Correct 357 ms 13292 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 7 ms 1004 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 1004 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 155 ms 8920 KB Output is correct
9 Correct 164 ms 5100 KB Output is correct
10 Correct 492 ms 13036 KB Output is correct
11 Correct 300 ms 13488 KB Output is correct
12 Correct 293 ms 13800 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 158 ms 9580 KB Output is correct
15 Correct 42 ms 2156 KB Output is correct
16 Correct 603 ms 13660 KB Output is correct
17 Correct 303 ms 13676 KB Output is correct
18 Correct 292 ms 13544 KB Output is correct
19 Correct 763 ms 97388 KB Output is correct
20 Correct 769 ms 94696 KB Output is correct
21 Correct 757 ms 97168 KB Output is correct
22 Correct 750 ms 94532 KB Output is correct
23 Correct 781 ms 94572 KB Output is correct
24 Correct 793 ms 94580 KB Output is correct
25 Correct 754 ms 94548 KB Output is correct
26 Correct 759 ms 97004 KB Output is correct
27 Correct 762 ms 97260 KB Output is correct
28 Correct 792 ms 94828 KB Output is correct
29 Correct 767 ms 94828 KB Output is correct
30 Correct 765 ms 94916 KB Output is correct