oj.uz

Submission #1043576

# Submission time Handle Problem Language Result Execution time Memory
1043576 2024-08-04T11:36:16 Z jcelin Radio Towers (IOI22_towers) C++17
17 / 100
 955 ms 182044 KB 
#pragma once 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = (1 << 30) - 1;
const ll INF = (1ll << 62) - 1;
const int logo = 17;
const int MAXN = 1e5 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

struct tour{
	int seg[trsz];
	
	void update(int x, int vl){
		x += off;
		seg[x] = vl;
		for(x /= 2; x; x /= 2) seg[x] = max(seg[x * 2], seg[x * 2 + 1]);
	}
	
	int query(int l, int r){
		int ret = 0;
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) ret = max(ret, seg[l++]);
			if(r & 1) ret = max(ret, seg[--r]);
		}
		return ret;
	}
	
	int spusti(int x, int vl, bool fl){
		if(x >= off) return x - off; 
		
		int pr = x * 2;
		if(fl) pr = x * 2 + 1;
		
		if(seg[pr] >= vl) return spusti(pr, vl, fl);
		return spusti(pr ^ 1, vl, fl);
	}
	
	int nadi(int l, int r, int vl, int fl){
		vi lef, rig;
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) lef.PB(l++);
			if(r & 1) rig.PB(--r);
		}
		while(rig.size()) lef.PB(rig.back()), rig.PPB();
		
		int ans = 0;
		if(fl == 0){			
			for(auto &x : lef){
				if(ans == 0 and seg[x] >= vl) ans = spusti(x, vl, 0);
			}	
		}else{				
			for(auto it = lef.rbegin(); it != lef.rend(); it++){
				if(ans == 0 and seg[*it] >= vl) ans = spusti(*it, vl, 1);
			}
		}
		
		return ans;
	}
}t;


struct tdelta{
	struct node{
		int v1, v2, ret1, ret2;
		
		node(){
			v1 = inf, v2 = -inf, ret1 = 0, ret2 = 0;
		}
	};
	
	node seg[trsz];
	
	node merge(node a, node b){
		node c;
		c.v1 = min(a.v1, b.v1);
		c.v2 = max(a.v2, b.v2);
		c.ret1 = max(a.ret1, b.ret1);
		c.ret1 = max(c.ret1, b.v2 - a.v1);
		
		c.ret2 = max(a.ret2, b.ret2);
		c.ret2 = max(c.ret2, a.v2 - b.v1);
		return c;
	}
	
	void update(int x, int vl){
		x += off;
		seg[x].v1 = seg[x].v2 = vl;
		for(x /= 2; x; x /= 2) seg[x] = merge(seg[x * 2], seg[x * 2 + 1]);
	}
	
	ii query(int l, int r){
		if(l > r) return {0, 0};
		node ret;
		vi lef, rig;
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) lef.PB(l++);
			if(r & 1) rig.PB(--r);
		}
		while(rig.size()) lef.PB(rig.back()), rig.PPB();
		for(auto &x : lef) ret = merge(ret, seg[x]);
		return {ret.ret1, ret.ret2};
	}
	
	int cm ;
	int spusti(int x, int vl){
		if(x >= off) return x - off;
		if(seg[x * 2].ret1 >= vl or seg[x * 2].v2 - cm >= vl) return spusti(x * 2, vl);
		cm = min(cm, seg[x * 2].v1);
		return spusti(x * 2 + 1, vl);
	}
	
	int nadi(int l, int r, int vl){
		vi lef, rig;
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) lef.PB(l++);
			if(r & 1) rig.PB(--r);
		}
		while(rig.size()) lef.PB(rig.back()), rig.PPB();
		
		cm = inf;
		int ret = inf;
		for(auto &x : lef){
			if(seg[x].ret1 >= vl or seg[x].v2 - cm >= vl){
				ret = spusti(x, vl);
				return ret;
			}
			cm = min(cm, seg[x].v1);
		}
	}
}del;

bool submit;

struct per{
	struct node{
		node *L, *R;
		int cnt, mi, mx;
		
		node(){
			L = R = 0;
			cnt = mi = mx = 0;
		}
		
		node(node *_L, node *_R, int _cnt, int _mi, int _mx){
			L = _L, R = _R, cnt = _cnt, mi = _mi, mx = _mx;
		}
	};
	
	typedef node* pnode;
	pnode rt[MAXN];
	set<pnode> st;
	
	pnode l(pnode x){return x ? x -> L : 0;}
	pnode r(pnode x){return x ? x -> R : 0;}
	int c(pnode x){return x ? x -> cnt : 0;}
	int sm(pnode x){return x ? x -> mi : 0;}
	int bg(pnode x){return x ? x -> mx : 0;}

	void update(pnode &x, int lo, int hi, int a, int b, int vl){
		if(lo >= b or hi <= a) return;
		if(!submit) st.insert(x);
		x = new node(l(x), r(x), c(x), sm(x), bg(x));
		if(!submit) st.insert(x);
		if(lo >= a and hi <= b){
			if(vl){
				x -> cnt = 1;
				x -> mi = lo;
				x -> mx = lo;
			}else{					
				x -> cnt = 0;
				x -> mi = inf;
				x -> mx = -inf;
			}
			return;
		}	
		int mid = (lo + hi) / 2;
		update(x -> L, lo, mid, a, b, vl);
		update(x -> R, mid, hi, a, b, vl);
		
		x -> mi = min(sm(x -> L), sm(x -> R));
		x -> mx = max(bg(x -> L), bg(x -> R));
		x -> cnt = c(x -> L) + c(x -> R);
	}
	
	int query(pnode &x, int lo, int hi, int a, int b){
		if(lo >= b or hi <= a or !x) return 0;
		if(lo >= a and hi <= b) return c(x);
		int mid = (lo + hi) / 2;
		return query(x -> L, lo, mid, a, b) + query(x -> R, mid, hi, a, b);
	}
	
	ii merge(ii a, ii b){
		return {min(a.X, b.X), max(a.Y, b.Y)};
	}
	
	ii qry(pnode &x, int lo, int hi, int a, int b){
		if(lo >= b or hi <= a or !x) return {inf, -inf};
		if(lo >= a and hi <= b) return {sm(x), bg(x)};
		int mid = (lo + hi) / 2;
		return merge(qry(x -> L, lo, mid, a, b), qry(x -> R, mid, hi, a, b));
	}
	
	void update(int tim, int a, int b, int vl){
		update(rt[tim], 0, off, a, b, vl);
	}
	
	void res(){
		for(auto &x : st) delete x;
		st.clear();
	}
	
	int query(int tim, int l, int r){
		return query(rt[tim], 0, off, l, r);
	}
	
	ii query2(int tim, int l, int r){
		return qry(rt[tim], 0, off, l, r);
	}
}p;


int pm[MAXN], pv[MAXN], vl[MAXN], arr[MAXN];
vii st;
vi upd[MAXN], vals;

void init(int n, vi aa){
	submit = 1;
	for(int i=0; i<n; i++) arr[i + 1] = aa[i];
	st.clear();
	arr[0] = 2 * inf;
	arr[n + 1] = 2 * inf;
	t.update(0, 2 * inf);
	t.update(n + 1, 2 * inf);
	st.PB({-1, -inf});
	for(int i=1; i<=n; i++){
		while(st.back().Y > arr[i]) st.PPB();
		pm[i] = st.back().X;
		st.PB({i, arr[i]});
		t.update(i, arr[i]);
		del.update(i, arr[i]);
	}
	
	st.clear();
	st.PB({n + 2, -inf});
	for(int i=n; i; i--){
		while(st.back().Y > arr[i]) st.PPB();
		pv[i] = st.back().X;
		st.PB({i, arr[i]});
	}
	
	
	for(int i=1; i<=n; i++){
		int a = pm[i], b = pv[i];
		int op = min(t.query(a + 1, i), t.query(i + 1, b));
		op = max(op, arr[i]);
		vl[i] = op - arr[i];
		vals.PB(vl[i]);
	}
	vals.PB(0);
	vals.PB(inf);
	sort(all(vals));
	vals.erase(unique(all(vals)), vals.end());
	for(int i=1; i<=n; i++){
		vl[i] = lower_bound(all(vals), vl[i]) - vals.begin();
		upd[vl[i] + 1].PB(i);
	}
	
	p.rt[0] = NULL;
	for(int i=1; i<=n; i++) p.update(0, i, i + 1, 1);
	
	for(int i=1; i<(int)vals.size(); i++){
		p.rt[i] = p.rt[i - 1];
		for(auto &x : upd[i]) p.update(i, x, x + 1, 0);
	}
}

int max_towers(int l, int r, int d){
	l++, r++;
	
	auto it = lower_bound(all(vals), d) - vals.begin();
	
	int lef, rig, sum = p.query(it, l, r + 1);
	
	if(sum == 0){
		if(l - r + 1 >= 3){
			int najl = del.nadi(l, r + 1, d);
			if(del.query(najl, r + 1).Y >= d) return 2;
		}
		return 1;
	}
	tie(lef, rig) = p.query2(it, l, r + 1);
	
	int opt = t.nadi(l, lef, arr[lef] + d, 1);
	if(opt) if(del.query(l, opt + 1).X >= d) sum++;
	
	opt = t.nadi(rig + 1, r + 1, arr[rig] + d, 0);
	if(opt) if(del.query(opt, r + 1).Y >= d) sum++;
	return sum;
}

void zavrsi(){
	p.res();
}

Compilation message

towers.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
towers.cpp: In member function 'int tdelta::nadi(int, int, int)':
towers.cpp:137:6: warning: control reaches end of non-void function [-Wreturn-type]
  137 |   vi lef, rig;
      |      ^~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 5 ms 12632 KB Output is correct
3 Correct 5 ms 12500 KB Output is correct
4 Correct 6 ms 12632 KB Output is correct
5 Correct 4 ms 12632 KB Output is correct
6 Correct 4 ms 12632 KB Output is correct
7 Correct 5 ms 12632 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 5 ms 12632 KB Output is correct
10 Correct 5 ms 12632 KB Output is correct
11 Correct 4 ms 12632 KB Output is correct
12 Incorrect 2 ms 9048 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 5 ms 12632 KB Output is correct
3 Correct 5 ms 12500 KB Output is correct
4 Correct 6 ms 12632 KB Output is correct
5 Correct 4 ms 12632 KB Output is correct
6 Correct 4 ms 12632 KB Output is correct
7 Correct 5 ms 12632 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 5 ms 12632 KB Output is correct
10 Correct 5 ms 12632 KB Output is correct
11 Correct 4 ms 12632 KB Output is correct
12 Incorrect 2 ms 9048 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 180244 KB Output is correct
2 Correct 902 ms 181452 KB Output is correct
3 Correct 771 ms 181404 KB Output is correct
4 Correct 830 ms 181936 KB Output is correct
5 Correct 880 ms 181964 KB Output is correct
6 Correct 854 ms 182044 KB Output is correct
7 Correct 827 ms 181996 KB Output is correct
8 Correct 786 ms 181444 KB Output is correct
9 Correct 815 ms 181444 KB Output is correct
10 Correct 905 ms 181188 KB Output is correct
11 Correct 955 ms 181184 KB Output is correct
12 Incorrect 793 ms 181444 KB 170th lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 50600 KB Output is correct
2 Correct 900 ms 181444 KB Output is correct
3 Correct 802 ms 181448 KB Output is correct
4 Correct 847 ms 181824 KB Output is correct
5 Correct 832 ms 181960 KB Output is correct
6 Correct 952 ms 181960 KB Output is correct
7 Correct 939 ms 181940 KB Output is correct
8 Correct 842 ms 181440 KB Output is correct
9 Correct 862 ms 181352 KB Output is correct
10 Correct 912 ms 181076 KB Output is correct
11 Correct 838 ms 181348 KB Output is correct
12 Correct 250 ms 181532 KB Output is correct
13 Correct 222 ms 182040 KB Output is correct
14 Correct 241 ms 181960 KB Output is correct
15 Correct 173 ms 181460 KB Output is correct
16 Correct 210 ms 180892 KB Output is correct
17 Correct 186 ms 175628 KB Output is correct
18 Correct 178 ms 181500 KB Output is correct
19 Correct 185 ms 181568 KB Output is correct
20 Correct 199 ms 181856 KB Output is correct
21 Correct 213 ms 181964 KB Output is correct
22 Correct 197 ms 181984 KB Output is correct
23 Correct 202 ms 181960 KB Output is correct
24 Correct 158 ms 181284 KB Output is correct
25 Correct 152 ms 181444 KB Output is correct
26 Correct 160 ms 180944 KB Output is correct
27 Correct 155 ms 181240 KB Output is correct
28 Correct 5 ms 12632 KB Output is correct
29 Correct 4 ms 12632 KB Output is correct
30 Correct 4 ms 12632 KB Output is correct
31 Correct 4 ms 12700 KB Output is correct
32 Correct 5 ms 12632 KB Output is correct
33 Correct 4 ms 10584 KB Output is correct
34 Correct 5 ms 12612 KB Output is correct
35 Correct 7 ms 12632 KB Output is correct
36 Correct 4 ms 12632 KB Output is correct
37 Correct 4 ms 12632 KB Output is correct
38 Correct 7 ms 12628 KB Output is correct
39 Correct 5 ms 12632 KB Output is correct
40 Correct 5 ms 12632 KB Output is correct
41 Correct 5 ms 12632 KB Output is correct
42 Correct 5 ms 12632 KB Output is correct
43 Correct 4 ms 12632 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 5 ms 12632 KB Output is correct
3 Correct 5 ms 12500 KB Output is correct
4 Correct 6 ms 12632 KB Output is correct
5 Correct 4 ms 12632 KB Output is correct
6 Correct 4 ms 12632 KB Output is correct
7 Correct 5 ms 12632 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 5 ms 12632 KB Output is correct
10 Correct 5 ms 12632 KB Output is correct
11 Correct 4 ms 12632 KB Output is correct
12 Incorrect 2 ms 9048 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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