oj.uz

Submission #654313

# Submission time Handle Problem Language Result Execution time Memory
654313 2022-10-30T23:26:03 Z resting Radio Towers (IOI22_towers) C++17
25 / 100
 3576 ms 538648 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long

#define mx 100005

struct tree {
	struct node {
		node(int l, int r) : l(l), r(r) {}
		int l = 0; int r = 0; int v = 0;
		node* lc = nullptr;
		node* rc = nullptr;
	};
	vector<node*> rt;
	vector<int> nums;

	tree() {
		nums.push_back(numeric_limits<int>::min());
		rt.push_back(build(0, mx));
	}
	void upd(int idx, int val, int v) {
		//cout << "index: " << idx << "," << "value: " << val << "," << "time: " << v << endl;
		nums.push_back(v); // v = time
		rt.push_back(upd2(rt.back(), idx, val));
	}

	node* build(int l, int r) {
		node* rt = new node(l, r);
		if (l == r) return rt;
		int m = (l + r) / 2;
		rt->lc = build(l, m);
		rt->rc = build(m + 1, r);
		return rt;
	}

	node* upd2(node* rt, int idx, int v) {
		//return the root
		if (rt->l > idx || rt->r < idx) return rt;
		node* tr = new node(*rt); //copy?
		if (tr->l == tr->r) {
			tr->v = v;
			return tr;
		}
		tr->lc = upd2(tr->lc, idx, v);
		tr->rc = upd2(tr->rc, idx, v);
		tr->v = tr->lc->v + tr->rc->v;
		return tr;
	}
	
	array<int, 3> query(int l, int r, int t) {
		node* vv = rt.at((upper_bound(nums.begin(), nums.end(), t) - nums.begin())-1);
		return { queryL(vv, l), queryR(vv, r), queryS(vv, l, r)};
	}

	int queryS(node* rt, int l, int r) {
		if (rt->l > r || rt->r < l)return 0;
		if (rt->l >= l && rt->r <= r) return rt->v;
		return queryS(rt->lc, l, r) + queryS(rt->rc, l, r);
	}

	int queryL(node* rt, int l) { //query left most with index >= l and value >= v
		if (rt->r < l) return -1;
		if (!rt->v) return -1;
		if (rt->l == rt->r) return rt->l;
		int res = queryL(rt->lc, l);
		return res == -1 ? queryL(rt->rc, l) : res;
	}

	int queryR(node* rt, int r) { //query right most with index <= r
		if (rt->l > r) return -1;
		if (!rt->v) return -1;
		if (rt->l == rt->r) return rt->l;
		int res = queryR(rt->rc, r);
		return res == -1 ? queryR(rt->lc, r) : res;
	}

} open, close;

vector<int> h;

//struct mintree { //ehh should be sparse tablebut wtv
//	struct node {
//		node(int l, int r) : l(l), r(r) {};
//		int v = numeric_limits<int>::max();
//		int l, r;
//		node *lc = 0, *rc = 0;
//	};
//	node* rt;
//	mintree() {
//		rt = build(0, mx);
//	}
//	node* build(int l, int r) {
//		node* rt = new node(l, r);
//		if (l == r) return rt;
//		int m = (l + r) / 2;
//		rt->lc = build(l, m);
//		rt->rc = build(m + 1, r);
//		return rt;
//	}
//	void upd(int i, int v) {
//		upd2(rt, i, v);
//	}
//	void upd2(node* rt, int i, int v) {
//		if (i < rt->l || i > rt->r) return;
//		if (rt->l == rt->r) {
//			rt->v = v;
//			return;
//		}
//		upd2(rt->lc, i, v); upd2(rt->rc, i, v);
//		rt->v = min(rt->lc->v, rt->rc->v);
//	}
//	int query(int l, int r) {
//		return query2(rt, l, r);
//	}
//	int query2(node* rt, int l, int r) {
//		if (l > rt->r || r < rt->l) return numeric_limits<int>::max();
//		if (rt->l >= l && rt->r <= r) return rt->v;
//		return min(query2(rt->lc, l, r), query2(rt->rc, l, r));
//	}
//} ac2;

#define ll int
struct difftree { //what the fk am i doing
	struct node {
		node(int l, int r) : l(l), r(r) {};
		ll mn = std::numeric_limits<int>::max()/2;
		ll ma = std::numeric_limits<int>::min()/2;
		ll incdif = 0, decdif = 0;
		int l, r;
		node* lc = 0, * rc = 0;
	};
	node* rt = 0;
	difftree() {
		rt = build(0, mx);
		//cout << rt->l << "," << rt->r << endl;
	}
	node* build(int l, int r) {
		node* rt = new node(l, r);
		if (l == r) return rt;
		int m = (l + r) / 2;
		rt->lc = build(l, m);
		rt->rc = build(m + 1, r);
		return rt;
	}
	void upd(int i, int v) {
		upd2(rt, i, v);
	}
	void upd2(node* rt, int i, int v) {
		if (i < rt->l || i > rt->r) return;
		if (rt->l == rt->r) {
			rt->mn = rt->ma = v;
			return;
		}
		upd2(rt->lc, i, v); upd2(rt->rc, i, v);
		rt->mn = min(rt->lc->mn, rt->rc->mn);
		rt->ma = max(rt->lc->ma, rt->rc->ma);
		rt->incdif = max(max(rt->lc->incdif, rt->rc->incdif), rt->rc->ma - rt->lc->mn);
		rt->decdif = max(max(rt->lc->decdif, rt->rc->decdif), rt->lc->ma - rt->rc->mn);
	}
	int incdif(int l, int r) {
		node amogus = query2(rt, l, r);
		int tmp = amogus.incdif;
		return tmp;
	}
	int decdif(int l, int r) {
		node amogus = query2(rt, l, r);
		int tmp = amogus.decdif;
		return tmp;
	}
	node query2(node* rt, int l, int r) {
		//cout << "gonna kms" << endl;
		//cout << l << "," << rt->l << "," << r << "," << rt->r << endl;
		if (l > rt->r || r < rt->l) return node(-1,-1);
		if (rt->l >= l && rt->r <= r) return *rt;
		node owo(-1, -1);
		node lc = query2(rt->lc, l, r);
		node rc = query2(rt->rc, l, r);
		owo.mn = min(lc.mn, rc.mn);
		owo.ma = max(lc.ma, rc.ma);
		owo.incdif = max(max(lc.incdif, rc.incdif), rc.ma - lc.mn);
		owo.decdif = max(max(lc.decdif, rc.decdif), lc.ma - rc.mn);
		return owo;
	}
} diff;
//
//struct dsu {
//	vector<int> p, r;
//	dsu() {
//		p.resize(mx, -1);
//		r.resize(mx, 0);
//	}
//	int par(int x) {
//		return p.at(x) == -1 ? x : p.at(x) = par(p.at(x));
//	}
//	void merge(int a, int b) {
//		a = par(a), b = par(b); 
//		if (a == b) return;
//		//attaching b to a, so r.at(a) must be bigger
//		if (r.at(a) < r.at(b)) swap(a, b);
//		if (r.at(a) == r.at(b)) r.at(a)++;
//		p.at(b) = a;
//	}
//};


void init(int N, vector<int> H) {
	h = H;
	h.insert(h.begin(), numeric_limits<int>::max()); N++;
	set<int> ranges;
	for (int i = 0; i < N; i++)
		ranges.insert(i);
	vector<int> mn = h;
	vector<bool> exists(N, 1);
	set<pair<int, int>> q;
	for (int i = 0; i < N; i++) {
		//ac2.upd(i, h.at(i));
		diff.upd(i, h.at(i));
		open.upd(i, 1, numeric_limits<int>::min());
		close.upd(i+1, 1, numeric_limits<int>::min());
		int v = numeric_limits<int>::max();
		if (i) v = min(v, h.at(i) - mn.at(i));
		if (i < N - 1)v = min(v, h.at(i + 1) - mn.at(i));
		q.insert({ v, i });
	}
	int time = numeric_limits<int>::min();
	while (q.size()) {
		auto [a, b] = *q.begin();
		time = max(time, a);
		q.erase(q.begin());
		if (!exists.at(b)) continue;

		auto x = ranges.find(b);
		if (b && h.at(b) - mn.at(b) <= a) {
			//deletus
			auto x2 = x; x2--;
			if (exists.at(*x2)) {
				exists.at(*x) = 0;
				open.upd(*x, 0, time);
				auto x3 = x; x3++;
				if (x3 == ranges.end()) close.upd(N, 0, time);
				else close.upd(*x3, 0, time);
				continue;
			}
			int tmp = mn.at(b);
			exists.at(*x) = 0; 
			exists.at(*x2) = 1;
			open.upd(*x, 0, time);
			open.upd(*x2, 1, time);
			ranges.erase(x--);
			mn.at(*x) = min(mn.at(*x), tmp);
		}
		else {
			auto x2 = x; x2++;
			//assert(x2 != ranges.end()); //troll
			if (x2 == ranges.end()) {
				continue;
			}
			if (exists.at(*x2)) {
				open.upd(*x, 0, time);
				close.upd(*x2, 0, time);
				exists.at(*x) = 0;
				continue;
			}
			if (x2 != ranges.end() && h.at(*x2) - mn.at(*x) <= a) {
				mn.at(*x) = min(mn.at(*x), mn.at(*x2));
				exists.at(*x2) = 0; 
				close.upd(*x2, 0, time);

				auto x3 = x2; x3++;
				if(x3 != ranges.end())close.upd(*x3, 1, time);
				else close.upd(N, 1, time);
				ranges.erase(x2);
			}
			else {
				break;
			}
		}
		//x is result

		b = *x; int v = numeric_limits<int>::max();
		if (b) v = min(v, h.at(b) - mn.at(b));
		x++;
		if (x != ranges.end()) v = min(v, h.at(*x) - mn.at(b));
		q.insert({ v, b });

		//yeahhhhhhh......
	}
	h = H;
}

int max_towers(int L, int R, int D) {
	L++, R++; D--;
	//this is so sus
	auto [a, b, c] = open.query(L, R, D);
	auto [e, f, g] = close.query(L, R, D);


	//auto .at(x, y, z) = open.query(0, 7, numeric_limits<int>::min());
	//cout << x << "," << y << "," << z << endl;
	//cout << c << "," << g << endl;

	if (e <= a) {
		g--;
	}
	if (b >= f) {
		c--;
	}
	if (c == 0 || g == 0) {
		//AMONGUS
		int l = L, r = R, m = 0;
		int inc = 0, dec = 0;
		while (l < r) {
			m = (l + r) / 2;
			 inc = diff.incdif(L, m);
			 dec = diff.decdif(m, R);
			//cout <<L<<","<<R<<","<<m << "," << inc << "," << dec << endl;
			if (min(inc, dec) >= D+1) break;
			if (max(inc, dec) < D + 1)break;
 			if (inc < dec)
				l = m + 1;
			else 
				r = m - 1;
		}
		//cout << "." << endl;
		if (min(inc, dec) >= D+1) {
			return 2;
		}
		else {
			return 1;
		}
	}
	//cout << a << "," << b << "," << c << endl;
	//cout << e << "," << f << "," << g << endl;
	//assert(a != -1);
	//assert(b != -1);
	//assert(e != -1);
	//assert(f != -1);

	
	//assert(c == g);
	//cout << diff.incdif(L, a) << "," << L << "," << a << endl;
	if (diff.incdif(L, a) >= D+1) c++;
	if (diff.decdif(f, R) >= D+1) c++;
	return c;
}

//
//int main() {
//	int N, Q;
//	assert(2 == scanf("%d %d", &N, &Q));
//	std::vector<int> H(N);
//	for (int i = 0; i < N; ++i) {
//		assert(1 == scanf("%d", &H.at(i)));
//	}
//	init(N, H);
//
//	for (int i = 0; i < Q; ++i) {
//		int L, R, D;
//		assert(3 == scanf("%d %d %d", &L, &R, &D));
//		printf("%d\n", max_towers(L, R, D));
//	}
//	return 0;
//}

Compilation message

towers.cpp:123: warning: "ll" redefined
  123 | #define ll int
      | 
towers.cpp:4: note: this is the location of the previous definition
    4 | #define ll long long
      |

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1056 ms 332284 KB 11th lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30544 KB Output is correct
2 Correct 40 ms 38512 KB Output is correct
3 Correct 37 ms 38616 KB Output is correct
4 Correct 37 ms 38676 KB Output is correct
5 Correct 38 ms 38600 KB Output is correct
6 Correct 38 ms 38524 KB Output is correct
7 Correct 38 ms 38608 KB Output is correct
8 Correct 40 ms 38672 KB Output is correct
9 Correct 44 ms 38592 KB Output is correct
10 Correct 37 ms 38472 KB Output is correct
11 Correct 44 ms 38504 KB Output is correct
12 Correct 23 ms 28428 KB Output is correct
13 Correct 37 ms 38636 KB Output is correct
14 Correct 37 ms 38604 KB Output is correct
15 Correct 37 ms 38600 KB Output is correct
16 Correct 38 ms 38580 KB Output is correct
17 Correct 37 ms 38600 KB Output is correct
18 Correct 37 ms 38584 KB Output is correct
19 Correct 36 ms 38620 KB Output is correct
20 Correct 38 ms 38608 KB Output is correct
21 Correct 38 ms 38512 KB Output is correct
22 Correct 39 ms 38504 KB Output is correct
23 Correct 38 ms 38588 KB Output is correct
24 Correct 36 ms 38552 KB Output is correct
25 Correct 30 ms 32968 KB Output is correct
26 Correct 38 ms 38632 KB Output is correct
27 Correct 38 ms 38492 KB Output is correct
28 Correct 38 ms 38508 KB Output is correct
29 Correct 39 ms 38580 KB Output is correct
30 Correct 37 ms 38624 KB Output is correct
31 Correct 37 ms 38576 KB Output is correct
32 Correct 36 ms 38660 KB Output is correct
33 Correct 38 ms 38588 KB Output is correct
34 Correct 36 ms 38604 KB Output is correct
35 Correct 37 ms 38600 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30544 KB Output is correct
2 Correct 40 ms 38512 KB Output is correct
3 Correct 37 ms 38616 KB Output is correct
4 Correct 37 ms 38676 KB Output is correct
5 Correct 38 ms 38600 KB Output is correct
6 Correct 38 ms 38524 KB Output is correct
7 Correct 38 ms 38608 KB Output is correct
8 Correct 40 ms 38672 KB Output is correct
9 Correct 44 ms 38592 KB Output is correct
10 Correct 37 ms 38472 KB Output is correct
11 Correct 44 ms 38504 KB Output is correct
12 Correct 23 ms 28428 KB Output is correct
13 Correct 37 ms 38636 KB Output is correct
14 Correct 37 ms 38604 KB Output is correct
15 Correct 37 ms 38600 KB Output is correct
16 Correct 38 ms 38580 KB Output is correct
17 Correct 37 ms 38600 KB Output is correct
18 Correct 37 ms 38584 KB Output is correct
19 Correct 36 ms 38620 KB Output is correct
20 Correct 38 ms 38608 KB Output is correct
21 Correct 38 ms 38512 KB Output is correct
22 Correct 39 ms 38504 KB Output is correct
23 Correct 38 ms 38588 KB Output is correct
24 Correct 36 ms 38552 KB Output is correct
25 Correct 30 ms 32968 KB Output is correct
26 Correct 38 ms 38632 KB Output is correct
27 Correct 38 ms 38492 KB Output is correct
28 Correct 38 ms 38508 KB Output is correct
29 Correct 39 ms 38580 KB Output is correct
30 Correct 37 ms 38624 KB Output is correct
31 Correct 37 ms 38576 KB Output is correct
32 Correct 36 ms 38660 KB Output is correct
33 Correct 38 ms 38588 KB Output is correct
34 Correct 36 ms 38604 KB Output is correct
35 Correct 37 ms 38600 KB Output is correct
36 Correct 626 ms 358624 KB Output is correct
37 Correct 960 ms 535612 KB Output is correct
38 Correct 987 ms 535588 KB Output is correct
39 Correct 1014 ms 535620 KB Output is correct
40 Correct 1020 ms 535648 KB Output is correct
41 Correct 1030 ms 535604 KB Output is correct
42 Correct 996 ms 535792 KB Output is correct
43 Correct 628 ms 538648 KB Output is correct
44 Correct 960 ms 535584 KB Output is correct
45 Correct 647 ms 532052 KB Output is correct
46 Incorrect 954 ms 535624 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
47 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2292 ms 532176 KB Output is correct
2 Correct 2443 ms 535640 KB Output is correct
3 Correct 2624 ms 535628 KB Output is correct
4 Correct 2526 ms 535512 KB Output is correct
5 Correct 2504 ms 535728 KB Output is correct
6 Correct 2447 ms 535624 KB Output is correct
7 Correct 2390 ms 535700 KB Output is correct
8 Correct 3097 ms 538444 KB Output is correct
9 Correct 3576 ms 535528 KB Output is correct
10 Correct 2311 ms 535512 KB Output is correct
11 Correct 2576 ms 535572 KB Output is correct
12 Correct 3157 ms 538488 KB Output is correct
13 Correct 3366 ms 535756 KB Output is correct
14 Correct 25 ms 28472 KB Output is correct
15 Correct 38 ms 38512 KB Output is correct
16 Correct 37 ms 38588 KB Output is correct
17 Correct 955 ms 535520 KB Output is correct
18 Correct 1035 ms 535636 KB Output is correct
19 Correct 1010 ms 535648 KB Output is correct
20 Correct 960 ms 535684 KB Output is correct
21 Correct 647 ms 538524 KB Output is correct
22 Correct 1068 ms 535472 KB Output is correct
23 Correct 1098 ms 535588 KB Output is correct
24 Correct 1086 ms 535760 KB Output is correct
25 Correct 1032 ms 535704 KB Output is correct
26 Correct 635 ms 534564 KB Output is correct
27 Correct 37 ms 38548 KB Output is correct
28 Correct 38 ms 38572 KB Output is correct
29 Correct 41 ms 38708 KB Output is correct
30 Correct 43 ms 38492 KB Output is correct
31 Correct 39 ms 38620 KB Output is correct
32 Correct 38 ms 38608 KB Output is correct
33 Correct 38 ms 38600 KB Output is correct
34 Correct 38 ms 38536 KB Output is correct
35 Correct 41 ms 38580 KB Output is correct
36 Correct 38 ms 38604 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 150076 KB Output is correct
2 Correct 2257 ms 535580 KB Output is correct
3 Correct 2352 ms 535580 KB Output is correct
4 Correct 2263 ms 535680 KB Output is correct
5 Incorrect 2290 ms 535568 KB 57037th lines differ - on the 1st token, expected: '2', found: '1'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30544 KB Output is correct
2 Correct 40 ms 38512 KB Output is correct
3 Correct 37 ms 38616 KB Output is correct
4 Correct 37 ms 38676 KB Output is correct
5 Correct 38 ms 38600 KB Output is correct
6 Correct 38 ms 38524 KB Output is correct
7 Correct 38 ms 38608 KB Output is correct
8 Correct 40 ms 38672 KB Output is correct
9 Correct 44 ms 38592 KB Output is correct
10 Correct 37 ms 38472 KB Output is correct
11 Correct 44 ms 38504 KB Output is correct
12 Correct 23 ms 28428 KB Output is correct
13 Correct 37 ms 38636 KB Output is correct
14 Correct 37 ms 38604 KB Output is correct
15 Correct 37 ms 38600 KB Output is correct
16 Correct 38 ms 38580 KB Output is correct
17 Correct 37 ms 38600 KB Output is correct
18 Correct 37 ms 38584 KB Output is correct
19 Correct 36 ms 38620 KB Output is correct
20 Correct 38 ms 38608 KB Output is correct
21 Correct 38 ms 38512 KB Output is correct
22 Correct 39 ms 38504 KB Output is correct
23 Correct 38 ms 38588 KB Output is correct
24 Correct 36 ms 38552 KB Output is correct
25 Correct 30 ms 32968 KB Output is correct
26 Correct 38 ms 38632 KB Output is correct
27 Correct 38 ms 38492 KB Output is correct
28 Correct 38 ms 38508 KB Output is correct
29 Correct 39 ms 38580 KB Output is correct
30 Correct 37 ms 38624 KB Output is correct
31 Correct 37 ms 38576 KB Output is correct
32 Correct 36 ms 38660 KB Output is correct
33 Correct 38 ms 38588 KB Output is correct
34 Correct 36 ms 38604 KB Output is correct
35 Correct 37 ms 38600 KB Output is correct
36 Correct 626 ms 358624 KB Output is correct
37 Correct 960 ms 535612 KB Output is correct
38 Correct 987 ms 535588 KB Output is correct
39 Correct 1014 ms 535620 KB Output is correct
40 Correct 1020 ms 535648 KB Output is correct
41 Correct 1030 ms 535604 KB Output is correct
42 Correct 996 ms 535792 KB Output is correct
43 Correct 628 ms 538648 KB Output is correct
44 Correct 960 ms 535584 KB Output is correct
45 Correct 647 ms 532052 KB Output is correct
46 Incorrect 954 ms 535624 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
47 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1056 ms 332284 KB 11th lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -