oj.uz

Submission #584049

# Submission time Handle Problem Language Result Execution time Memory
584049 2022-06-26T17:13:36 Z BackNoob Wall (IOI14_wall) C++14
100 / 100
 1025 ms 99276 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
struct IT{
	int n;
	vector<int> tmax, tmin;

	IT(){}
	IT(int _n) 
	{
		n = _n;
		tmax.resize(n * 4 + 7, 0);
		tmin.resize(n * 4 + 7, 0);
	}

	void push_down(int v)
	{
		maximize(tmax[v * 2], tmax[v]);
		maximize(tmax[v * 2 + 1], tmax[v]);
		minimize(tmin[v * 2], tmin[v]);
		minimize(tmin[v * 2 + 1], tmin[v]);

		if(tmax[v * 2] > tmin[v * 2]) {
			if(tmax[v * 2] == tmax[v]) 
				maximize(tmin[v * 2], tmax[v * 2]);
			else 
				minimize(tmax[v * 2], tmin[v * 2]);

		}

		if(tmax[v * 2 + 1] > tmin[v * 2 + 1]) {
			if(tmax[v * 2 + 1] == tmax[v]) 
				maximize(tmin[v * 2 + 1], tmax[v * 2 + 1]);
			else 
				minimize(tmax[v * 2 + 1], tmin[v * 2 + 1]);
		}
	}

	void update_min(int v, int tl, int tr, int l, int r, int val)
	{
		if(l > r) return ;
		if(tl == l && tr == r) {
			tmin[v] = min(tmin[v], val);
			tmax[v] = min(tmax[v], val);
		}
		else {
			int tm = (tl + tr) / 2;
			push_down(v);
			update_min(v * 2, tl, tm, l, min(r, tm), val);
			update_min(v * 2 + 1, tm + 1 , tr, max(l, tm + 1), r, val);
			tmin[v] = max(tmin[v * 2], tmin[v * 2 + 1]);
			tmax[v] = min(tmax[v * 2], tmax[v * 2 + 1]);
		}
	}

	void update_max(int v, int tl, int tr, int l, int r, int val)
	{
		if(l > r) return ;
		if(tl == l && tr == r) {
			tmax[v] = max(tmax[v], val);
			tmin[v] = max(tmin[v], tmax[v]);
		}
		else {
			int tm = (tl + tr) / 2;
			push_down(v);
			update_max(v * 2, tl, tm, l, min(r, tm), val);
			update_max(v * 2 + 1, tm + 1 , tr, max(l, tm + 1), r, val);
			tmin[v] = max(tmin[v * 2], tmin[v * 2 + 1]);
			tmax[v] = min(tmax[v * 2], tmax[v * 2 + 1]);
		}
	}

	void update_min(int l, int r, int val)
	{
		update_min(1, 1, n, l, r, val);
	}

	void update_max(int l, int r, int val)
	{
		update_max(1, 1, n, l, r, val);
	}
	int getans(int v, int tl, int tr, int pos)
	{
		if(tl == tr) return tmax[v];
		else {
			int tm = (tl + tr) / 2;
			push_down(v);
			if(pos <= tm) return getans(v * 2, tl, tm, pos);
			else return getans(v * 2 + 1, tm + 1, tr, pos);
		}
	}
	int getans(int pos)
	{
		return getans(1, 1, n, pos);
	}
} seg;
 

void buildWall(int n, int q, int op[], int lef[], int rig[], int h[], int ans[])
{
	seg = IT(n);
	for(int i = 1; i <= q; i++) {
		if(op[i - 1] == 1) seg.update_max(lef[i - 1] + 1, rig[i - 1] + 1, h[i - 1]);
		if(op[i - 1] == 2) seg.update_min(lef[i - 1] + 1, rig[i - 1] + 1, h[i - 1]);	
	}

	for(int i = 1; i <= n; i++) ans[i - 1] = seg.getans(i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 824 KB Output is correct
5 Correct 6 ms 832 KB Output is correct
6 Correct 5 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 147 ms 13856 KB Output is correct
3 Correct 195 ms 7956 KB Output is correct
4 Correct 455 ms 21516 KB Output is correct
5 Correct 312 ms 22388 KB Output is correct
6 Correct 286 ms 20888 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 8 ms 820 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 6 ms 828 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 129 ms 13940 KB Output is correct
9 Correct 163 ms 7960 KB Output is correct
10 Correct 446 ms 21512 KB Output is correct
11 Correct 294 ms 22476 KB Output is correct
12 Correct 298 ms 20876 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 130 ms 13860 KB Output is correct
15 Correct 36 ms 1960 KB Output is correct
16 Correct 567 ms 21644 KB Output is correct
17 Correct 361 ms 21068 KB Output is correct
18 Correct 296 ms 21116 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 6 ms 828 KB Output is correct
6 Correct 6 ms 824 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 132 ms 13908 KB Output is correct
9 Correct 177 ms 8012 KB Output is correct
10 Correct 481 ms 21348 KB Output is correct
11 Correct 333 ms 22440 KB Output is correct
12 Correct 294 ms 20932 KB Output is correct
13 Correct 0 ms 304 KB Output is correct
14 Correct 137 ms 13944 KB Output is correct
15 Correct 42 ms 1924 KB Output is correct
16 Correct 641 ms 21732 KB Output is correct
17 Correct 324 ms 21024 KB Output is correct
18 Correct 303 ms 21064 KB Output is correct
19 Correct 1014 ms 99276 KB Output is correct
20 Correct 1025 ms 96676 KB Output is correct
21 Correct 1010 ms 99192 KB Output is correct
22 Correct 990 ms 96776 KB Output is correct
23 Correct 997 ms 96804 KB Output is correct
24 Correct 1018 ms 96764 KB Output is correct
25 Correct 959 ms 96676 KB Output is correct
26 Correct 984 ms 99276 KB Output is correct
27 Correct 1010 ms 99232 KB Output is correct
28 Correct 994 ms 96740 KB Output is correct
29 Correct 997 ms 96716 KB Output is correct
30 Correct 973 ms 96728 KB Output is correct