oj.uz

Submission #1079375

# Submission time Handle Problem Language Result Execution time Memory
1079375 2024-08-28T13:38:51 Z vjudge1 Wall (IOI14_wall) C++17
0 / 100
 3 ms 860 KB 
#include<bits/stdc++.h>
using namespace std;
#include "wall.h"

const int maxn = 2e6 + 5, inf = 1e9 + 5;
int mi[maxn << 2], mx[maxn << 2], N, res[maxn];
pair<int, int> lazy[maxn << 2];

void pull_inc(int id, int k) {
	mi[id] = max(mi[id], k);
	mx[id] = max(mx[id], k);
	lazy[id].first = max(lazy[id].first, k);
	lazy[id].second = max(lazy[id].second, k);
}

void pull_dec(int id, int k) {
	mi[id] = min(mi[id], k);
	mx[id] = min(mx[id], k);
	lazy[id].first = min(lazy[id].first, k);
	lazy[id].second = min(lazy[id].second, k);
}

void shift(int id){
    if(lazy[id].first != -inf){
        pull_inc(id << 1, lazy[id].first);
        pull_inc(id << 1 | 1, lazy[id].first);
    }
    if(lazy[id].second != inf){
        pull_dec(id << 1, lazy[id].second);
        pull_dec(id << 1 | 1, lazy[id].second);
    }
    lazy[id] = {-inf, inf};
}

void upd(int L, int R, int k, int t, int id = 1, int tl = 0, int tr = N - 1) {
	if (L > tr || R < tl) return;
	if (L <= tl && R >= tr) {
		if (t == 1) pull_inc(id, k);
		else pull_dec(id, k);
	}
	shift(id);
	upd(L, R, k, t, id << 1, tl, (tl + tr) >> 1);
	upd(L, R, k, t, id << 1 | 1, ((tl + tr) >> 1) + 1, tr);
	mi[id] = min(mi[id << 1], mi[id << 1 | 1]);
	mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}

void get(int id = 1, int tl = 0, int tr = N - 1) {
	if (tl == tr) { res[tl] = mi[id]; return; }
	shift(id);
	get(id << 1, tl, (tl + tr) >> 1);
	get(id << 1 | 1, ((tl + tr) >> 1) + 1, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	N = n;
	for (int i = 0; i < k; i++) upd(left[i], right[i], height[i], op[i]);
	get();
	for (int i = 0; i < N; i++) finalHeight[i] = res[i];
	return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -