oj.uz

Submission #1009975

# Submission time Handle Problem Language Result Execution time Memory
1009975 2024-06-28T08:37:43 Z stdfloat Wall (IOI14_wall) C++17
24 / 100
 764 ms 26964 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

#define ff  first
#define ss  second
#define pii pair<int, int>

vector<int> st;

vector<pair<pii, pii>> lz;

void Lz(int nd, pii p) {
    if ((lz[nd].ff.ff == 1 && p.ff == 1 && lz[nd].ff.ss <= p.ss) || (lz[nd].ff.ff == 2 && p.ff == 2 && lz[nd].ff.ss >= p.ss)) lz[nd].ff = {-1, -1};
    if ((lz[nd].ss.ff == 1 && p.ff == 1 && lz[nd].ss.ss <= p.ss) || (lz[nd].ss.ff == 2 && p.ff == 2 && lz[nd].ss.ss >= p.ss)) lz[nd].ss = {-1, -1};

    if (lz[nd].ff.ff == p.ff || lz[nd].ss.ff == p.ff) return;

    if (lz[nd].ff == (pii){-1, -1}) lz[nd].ff = p;
    else if (lz[nd].ss == (pii){-1, -1}) lz[nd].ss = p;
	else {
		if (lz[nd].ff.ff == 2) lz[nd].ff.ss = max(lz[nd].ff.ss, lz[nd].ss.ss);
		else lz[nd].ff.ss = min(lz[nd].ff.ss, lz[nd].ss.ss);
	}
}

void LZ(int nd, int l, int r) {
    if (lz[nd].ff.ff == 1) st[nd] = max(st[nd], lz[nd].ff.ss);
    else if (lz[nd].ff.ff == 2) st[nd] = min(st[nd], lz[nd].ff.ss);
    
    if (lz[nd].ss.ff == 1) st[nd] = max(st[nd], lz[nd].ss.ss);
    else if (lz[nd].ss.ff == 2) st[nd] = min(st[nd], lz[nd].ss.ss);

	if (l < r) {
		int ch = (nd << 1) + 1;
        if (lz[nd].ff != (pii){-1, -1}) {
            Lz(ch, lz[nd].ff); Lz(ch + 1, lz[nd].ff);
        }
        if (lz[nd].ss != (pii){-1, -1}) {
            Lz(ch, lz[nd].ss); Lz(ch + 1, lz[nd].ss);
        }
	}

    lz[nd].ff = lz[nd].ss = {-1, -1};
}

int upd(int nd, int l, int r, int x, int y, int op, int h) {
	LZ(nd, l, r);

	if (r < x || y < l) return st[nd];

	if (x <= l && r <= y) {
		Lz(nd, {op, h}); LZ(nd, l, r);
		return st[nd];
	}

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return st[nd] = max(upd(ch, l, md, x, y, op, h), upd(ch + 1, md + 1, r, x, y, op, h));
}

int fnd(int nd, int l, int r, int x) {
	LZ(nd, l, r);

	if (r < x || x < l) return 0;

	if (l == r) return st[nd];

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return max(fnd(ch, l, md, x), fnd(ch + 1, md + 1, r, x));
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]) {
	st.assign(n << 2, 0);
	lz.assign(n << 2, {});

    for (auto &i : lz) {
        i.ff = i.ss = {-1, -1};
    }

	for (int i = 0; i < k; i++) {
        upd(0, 0, n - 1, l[i], r[i], op[i], h[i]);
    }

	for (int i = 0; i < n; i++) {
        fh[i] = fnd(0, 0, n - 1, i);
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 2 ms 408 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 85 ms 14036 KB Output is correct
3 Correct 299 ms 8944 KB Output is correct
4 Correct 764 ms 26144 KB Output is correct
5 Correct 272 ms 26964 KB Output is correct
6 Correct 264 ms 25584 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 3 ms 444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -