oj.uz

Submission #899414

# Submission time Handle Problem Language Result Execution time Memory
899414 2024-01-06T06:19:29 Z ByeWorld Wall (IOI14_wall) C++14
100 / 100
 724 ms 161180 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 2e6+10;
const int INF = 2e9+10;

int n, k;
int ans[MAXN];

struct node {
	int sum;
	int mx, mx2, mxc;
	int mn, mn2, mnc;
} st[4*MAXN];

struct seg {
	void merge(int id){
		st[id].sum = st[lf].sum + st[rg].sum;

		// mx
		if(st[lf].mx == st[rg].mx){
			st[id].mx = st[lf].mx;
			st[id].mxc = st[lf].mxc + st[rg].mxc;

			st[id].mx2 = max(st[lf].mx2, st[rg].mx2);

		} else if(st[lf].mx > st[rg].mx){
			st[id].mx = st[lf].mx;
			st[id].mxc = st[lf].mxc;

			st[id].mx2 = max(st[lf].mx2, st[rg].mx);
		} else {
			// st[lf].mx < st[rg].mx
			st[id].mx = st[rg].mx;
			st[id].mxc = st[rg].mxc;

			st[id].mx2 = max(st[lf].mx, st[rg].mx2);
		}

		// mn 
		if(st[lf].mn == st[rg].mn){
			st[id].mn = st[lf].mn;
			st[id].mnc = st[lf].mnc + st[rg].mnc;

			st[id].mn2 = min(st[lf].mn2, st[rg].mn2);

		} else if(st[lf].mn < st[rg].mn){
			st[id].mn = st[lf].mn;
			st[id].mnc = st[lf].mnc;

			st[id].mn2 = min(st[lf].mn2, st[rg].mn);
		} else {
			// st[lf].mn > st[rg].mn
			st[id].mn = st[rg].mn;
			st[id].mnc = st[rg].mnc;

			st[id].mn2 = min(st[lf].mn, st[rg].mn2);
		}
	}


	void bd(int id, int l, int r){
		if(l==r){ 
			st[id].sum = st[id].mx = st[id].mn = 0; 
			st[id].mx2 = -INF; st[id].mn2 = INF;
			st[id].mxc = st[id].mnc = 1;
			return; 
		}
		bd(lf, l, md); bd(rg, md+1, r);
		merge(id);
		//cout << l << ' ' << r << ' ' << st[id].mx << ' ' << st[id].mx2 << " lrx\n";
	}

	void push_mx(int id, int p, bool len){
		if(p <= st[id].mn) return;
 		st[id].sum += (p-st[id].mn) * st[id].mnc; // jadi makin gede
		st[id].mn = p;

		// mx nya gmn?
		if(len){ // l == r
			st[id].mx = p;
		} else {
			if(p >= st[id].mx) st[id].mx = p;
			else if(p > st[id].mx2) st[id].mx2 = p;
		}
	}
	void push_mn(int id, int p, bool len){
		if(p >= st[id].mx) return;
 		st[id].sum += (p-st[id].mx) * st[id].mxc; // jadi makin kecil, minus
		st[id].mx = p;

		// mn nya gmn?
		if(len){
			st[id].mn = p;
		} else {
			if(p <= st[id].mn) st[id].mn = p;
			else if(p < st[id].mn2) st[id].mn2 = p;
		}
	}

	void bnc(int id, int l, int r){
		if(l == r) return;
		push_mn(lf, st[id].mx, l == md); // new value yg ke prop
		push_mn(rg, st[id].mx, md+1 == r);

		//cout << "here\n";
		push_mx(lf, st[id].mn, l == md); 
		push_mx(rg, st[id].mn, md+1 == r);
	}

	void CHMX(int id, int l, int r, int x, int y, int p){ //a[i] = max(a[i], x);
		if(r<x || y<l || p <= st[id].mn) return; // update gk ganti apa2
		//cout << l << ' ' << r << ' ' << st[id].mn << ' ' << st[id].mn2 << " lr\n";

		if(x<=l && r<=y && p < st[id].mn2){
			push_mx(id, p, l==r);
			return;
		}
		bnc(id, l, r);

		CHMX(lf, l, md, x, y, p); CHMX(rg, md+1, r, x, y, p);
		merge(id);
	}
	void CHMN(int id, int l, int r, int x, int y, int p){ //a[i] = min(a[i], x)
		if(r<x || y<l || p >= st[id].mx) return; // update gk ganti apa2
		//cout << l << ' ' << r << ' ' << st[id].mx << ' ' << st[id].mx2 << " lr\n";
		if(x<=l && r<=y && p > st[id].mx2){ // mx masih ttp mx, tp ganti jadi x -> mx = x
			push_mn(id, p, l==r);
			return;
		}
		bnc(id, l, r);

		CHMN(lf, l, md, x, y, p); CHMN(rg, md+1, r, x, y, p);

		merge(id);
	}	

	void que(int id, int l, int r){
		if(l==r){ 
			ans[l] = st[id].sum; 
			//cout << l << ' ' << ans[l] << " p\n"; 
			return; 
		}
		bnc(id, l, r);
		que(lf, l, md); que(rg, md+1, r);
	}
} A;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	
	A.bd(1, 1, n);
	for(int i=0; i<k; i++){
		if(op[i] == 1){ // add -> a[i] = max(a[i], x);
			A.CHMX(1, 1, n, left[i]+1, right[i]+1, height[i]);
		} else { // remove -> a[i] = min(a[i], x)
			A.CHMN(1, 1, n, left[i]+1, right[i]+1, height[i]);
		}
	}

	A.que(1, 1, n);
	for(int i=1; i<=n; i++) finalHeight[i-1] = ans[i];
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 4 ms 2648 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 6 ms 4812 KB Output is correct
5 Correct 5 ms 4956 KB Output is correct
6 Correct 5 ms 4956 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 107 ms 10320 KB Output is correct
3 Correct 56 ms 8012 KB Output is correct
4 Correct 142 ms 28844 KB Output is correct
5 Correct 176 ms 30040 KB Output is correct
6 Correct 186 ms 28336 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 6 ms 4956 KB Output is correct
5 Correct 5 ms 4956 KB Output is correct
6 Correct 5 ms 4912 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 109 ms 16064 KB Output is correct
9 Correct 57 ms 11736 KB Output is correct
10 Correct 142 ms 28692 KB Output is correct
11 Correct 154 ms 29928 KB Output is correct
12 Correct 179 ms 28204 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 113 ms 16104 KB Output is correct
15 Correct 33 ms 5668 KB Output is correct
16 Correct 538 ms 28920 KB Output is correct
17 Correct 330 ms 28532 KB Output is correct
18 Correct 288 ms 28500 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 8 ms 4908 KB Output is correct
5 Correct 5 ms 4956 KB Output is correct
6 Correct 5 ms 4740 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 109 ms 16120 KB Output is correct
9 Correct 57 ms 11620 KB Output is correct
10 Correct 146 ms 28660 KB Output is correct
11 Correct 161 ms 29752 KB Output is correct
12 Correct 179 ms 28244 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 112 ms 15956 KB Output is correct
15 Correct 33 ms 5712 KB Output is correct
16 Correct 562 ms 29144 KB Output is correct
17 Correct 293 ms 28668 KB Output is correct
18 Correct 290 ms 28504 KB Output is correct
19 Correct 671 ms 161104 KB Output is correct
20 Correct 708 ms 158688 KB Output is correct
21 Correct 674 ms 161180 KB Output is correct
22 Correct 694 ms 158636 KB Output is correct
23 Correct 671 ms 158816 KB Output is correct
24 Correct 680 ms 158536 KB Output is correct
25 Correct 689 ms 156852 KB Output is correct
26 Correct 724 ms 161180 KB Output is correct
27 Correct 674 ms 161172 KB Output is correct
28 Correct 701 ms 158680 KB Output is correct
29 Correct 697 ms 158380 KB Output is correct
30 Correct 710 ms 158616 KB Output is correct