oj.uz

Submission #986565

# Submission time Handle Problem Language Result Execution time Memory
986565 2024-05-20T18:27:15 Z vqpahmad Wall (IOI14_wall) C++14
100 / 100
 584 ms 69640 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int off = (1<<21);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
	pii t[off * 2];
	pii unit = {0, inf};
	void init(){
		for (int i = 0; i < off * 2; i++){
			t[i] = unit;
		}
	}
	pii merge(pii lhs, pii rhs){
		// lhs.S     rhs.S
		// lhs.F     rhs.F
		if (lhs.F > rhs.S){
			return {rhs.S, rhs.S};
		}
		if (rhs.F > lhs.S){
			return {rhs.F, rhs.F};
		}
		return {max(lhs.F, rhs.F), min(lhs.S, rhs.S)};
	}
	void push(int idx){
		if (t[idx] == unit || idx >= off) return;
		t[ls] = merge(t[ls], t[idx]);
		t[rs] = merge(t[rs], t[idx]);
		t[idx] = unit;
	}
	void update(int l, int r, int op, int val, int idx=1, int lo=0, int hi=off){
		push(idx);
		if (r <= lo || hi <= l) 
			return;
		if (l <= lo && hi <= r){
			if (op == 1){
				t[idx] = merge(t[idx], {val, inf});
			} else if (op == 2){
				t[idx] = merge(t[idx], {0, val});
			}
			return;
		}
		int mi = (lo+hi)>>1;
		update(l, r, op, val, ls, lo, mi);
		update(l, r, op, val, rs, mi, hi);
		return;
	}
	void updateAll(){
		for (int i = 0; i < off; i++){
			push(i);
		}
	}
	void printO(){
		int pw = 1;
		int cnt = 0;
		for (int i = 1; i < off * 2; i++){
			cnt++;
			cout << "("<< (t[i].F == inf ? -1 : t[i].F) << ", " << (t[i].S == inf ? -1 : t[i].S) << ") ";
			if (cnt == pw){
				pw *= 2;
				cnt = 0 ;
				cout << endl;
			}
		}
	}
	void print(int n){
		
		updateAll();
		for (int i = 0; i < n; i++){
			cout << "("<< (t[i + off].F == inf ? -1 : t[i + off].F) << ", " << (t[i + off].S == inf ? -1 : t[i + off].S) << ") ";
		}
		cout << endl;
	}
} seg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	seg.init();
	//seg.printO();
	for (int i = 0; i < k; i++){
		seg.update(left[i], right[i] + 1, op[i], height[i]);
		//seg.printO();
		//seg.print(n);
	}
	seg.updateAll();
	for (int i = 0; i < n; i++){
		finalHeight[i] = seg.t[i + off].F;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33200 KB Output is correct
2 Correct 22 ms 33368 KB Output is correct
3 Correct 22 ms 33104 KB Output is correct
4 Correct 25 ms 33372 KB Output is correct
5 Correct 24 ms 33624 KB Output is correct
6 Correct 22 ms 33368 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33116 KB Output is correct
2 Correct 192 ms 46900 KB Output is correct
3 Correct 171 ms 38992 KB Output is correct
4 Correct 438 ms 51096 KB Output is correct
5 Correct 235 ms 52332 KB Output is correct
6 Correct 231 ms 50768 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 33112 KB Output is correct
2 Correct 21 ms 33368 KB Output is correct
3 Correct 21 ms 33300 KB Output is correct
4 Correct 25 ms 33372 KB Output is correct
5 Correct 25 ms 33616 KB Output is correct
6 Correct 23 ms 33372 KB Output is correct
7 Correct 19 ms 33464 KB Output is correct
8 Correct 205 ms 46672 KB Output is correct
9 Correct 167 ms 40212 KB Output is correct
10 Correct 421 ms 51212 KB Output is correct
11 Correct 247 ms 52260 KB Output is correct
12 Correct 229 ms 50772 KB Output is correct
13 Correct 19 ms 33264 KB Output is correct
14 Correct 226 ms 46676 KB Output is correct
15 Correct 51 ms 34304 KB Output is correct
16 Correct 584 ms 51476 KB Output is correct
17 Correct 251 ms 50892 KB Output is correct
18 Correct 240 ms 50772 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33116 KB Output is correct
2 Correct 22 ms 33356 KB Output is correct
3 Correct 21 ms 33280 KB Output is correct
4 Correct 24 ms 33368 KB Output is correct
5 Correct 22 ms 33372 KB Output is correct
6 Correct 23 ms 33488 KB Output is correct
7 Correct 19 ms 33112 KB Output is correct
8 Correct 192 ms 46784 KB Output is correct
9 Correct 163 ms 40272 KB Output is correct
10 Correct 420 ms 51284 KB Output is correct
11 Correct 235 ms 52276 KB Output is correct
12 Correct 233 ms 50592 KB Output is correct
13 Correct 19 ms 33112 KB Output is correct
14 Correct 194 ms 46816 KB Output is correct
15 Correct 53 ms 34300 KB Output is correct
16 Correct 565 ms 51468 KB Output is correct
17 Correct 240 ms 50768 KB Output is correct
18 Correct 245 ms 50892 KB Output is correct
19 Correct 506 ms 69628 KB Output is correct
20 Correct 481 ms 66896 KB Output is correct
21 Correct 491 ms 69448 KB Output is correct
22 Correct 480 ms 67140 KB Output is correct
23 Correct 482 ms 67140 KB Output is correct
24 Correct 487 ms 67088 KB Output is correct
25 Correct 493 ms 67452 KB Output is correct
26 Correct 490 ms 69456 KB Output is correct
27 Correct 488 ms 69640 KB Output is correct
28 Correct 500 ms 66896 KB Output is correct
29 Correct 495 ms 67152 KB Output is correct
30 Correct 495 ms 67184 KB Output is correct