oj.uz

Submission #986785

# Submission time Handle Problem Language Result Execution time Memory
986785 2024-05-21T08:20:01 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 632 ms 69632 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 21 ms 33112 KB Output is correct
2 Correct 23 ms 33368 KB Output is correct
3 Correct 23 ms 33112 KB Output is correct
4 Correct 32 ms 33440 KB Output is correct
5 Correct 25 ms 33372 KB Output is correct
6 Correct 29 ms 33368 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33112 KB Output is correct
2 Correct 201 ms 46868 KB Output is correct
3 Correct 170 ms 39104 KB Output is correct
4 Correct 431 ms 51312 KB Output is correct
5 Correct 234 ms 52304 KB Output is correct
6 Correct 240 ms 50572 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33112 KB Output is correct
2 Correct 23 ms 33624 KB Output is correct
3 Correct 22 ms 33112 KB Output is correct
4 Correct 26 ms 33372 KB Output is correct
5 Correct 23 ms 33368 KB Output is correct
6 Correct 24 ms 33364 KB Output is correct
7 Correct 20 ms 33104 KB Output is correct
8 Correct 195 ms 46712 KB Output is correct
9 Correct 167 ms 40364 KB Output is correct
10 Correct 426 ms 51216 KB Output is correct
11 Correct 238 ms 52304 KB Output is correct
12 Correct 230 ms 50648 KB Output is correct
13 Correct 20 ms 33112 KB Output is correct
14 Correct 199 ms 46928 KB Output is correct
15 Correct 53 ms 34384 KB Output is correct
16 Correct 588 ms 51472 KB Output is correct
17 Correct 240 ms 50896 KB Output is correct
18 Correct 243 ms 50760 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33112 KB Output is correct
2 Correct 22 ms 33360 KB Output is correct
3 Correct 22 ms 33112 KB Output is correct
4 Correct 29 ms 33620 KB Output is correct
5 Correct 25 ms 33368 KB Output is correct
6 Correct 24 ms 33624 KB Output is correct
7 Correct 21 ms 33124 KB Output is correct
8 Correct 196 ms 46964 KB Output is correct
9 Correct 172 ms 40356 KB Output is correct
10 Correct 424 ms 51280 KB Output is correct
11 Correct 239 ms 52172 KB Output is correct
12 Correct 285 ms 50636 KB Output is correct
13 Correct 23 ms 33112 KB Output is correct
14 Correct 197 ms 46728 KB Output is correct
15 Correct 65 ms 34384 KB Output is correct
16 Correct 632 ms 51464 KB Output is correct
17 Correct 253 ms 50744 KB Output is correct
18 Correct 258 ms 50740 KB Output is correct
19 Correct 526 ms 69632 KB Output is correct
20 Correct 512 ms 66952 KB Output is correct
21 Correct 519 ms 69448 KB Output is correct
22 Correct 519 ms 67140 KB Output is correct
23 Correct 505 ms 66908 KB Output is correct
24 Correct 524 ms 66916 KB Output is correct
25 Correct 512 ms 67020 KB Output is correct
26 Correct 539 ms 69440 KB Output is correct
27 Correct 522 ms 69448 KB Output is correct
28 Correct 495 ms 67100 KB Output is correct
29 Correct 508 ms 67144 KB Output is correct
30 Correct 497 ms 67140 KB Output is correct