oj.uz

Submission #1043502

# Submission time Handle Problem Language Result Execution time Memory
1043502 2024-08-04T10:15:51 Z jcelin Radio Towers (IOI22_towers) C++17
0 / 100
 919 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){
		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};
	}
}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();
	st.PB({0, -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 + 1, -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) 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
      |         ^~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 384 ms 111748 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 4 ms 12632 KB Output is correct
3 Correct 4 ms 12632 KB Output is correct
4 Correct 4 ms 12596 KB Output is correct
5 Correct 4 ms 12632 KB Output is correct
6 Correct 7 ms 12632 KB Output is correct
7 Correct 8 ms 12632 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 4 ms 12632 KB Output is correct
10 Correct 4 ms 12652 KB Output is correct
11 Correct 5 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 4 ms 12632 KB Output is correct
3 Correct 4 ms 12632 KB Output is correct
4 Correct 4 ms 12596 KB Output is correct
5 Correct 4 ms 12632 KB Output is correct
6 Correct 7 ms 12632 KB Output is correct
7 Correct 8 ms 12632 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 4 ms 12632 KB Output is correct
10 Correct 4 ms 12652 KB Output is correct
11 Correct 5 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 652 ms 180164 KB Output is correct
2 Correct 818 ms 181448 KB Output is correct
3 Correct 919 ms 181380 KB Output is correct
4 Correct 823 ms 181960 KB Output is correct
5 Correct 822 ms 182044 KB Output is correct
6 Correct 841 ms 181924 KB Output is correct
7 Correct 835 ms 181960 KB Output is correct
8 Correct 753 ms 181448 KB Output is correct
9 Correct 840 ms 181444 KB Output is correct
10 Correct 912 ms 181188 KB Output is correct
11 Correct 878 ms 181188 KB Output is correct
12 Incorrect 759 ms 181444 KB 170th lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 50256 KB Output is correct
2 Correct 888 ms 181636 KB Output is correct
3 Incorrect 808 ms 181396 KB 69174th lines differ - on the 1st token, expected: '2', found: '1'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 4 ms 12632 KB Output is correct
3 Correct 4 ms 12632 KB Output is correct
4 Correct 4 ms 12596 KB Output is correct
5 Correct 4 ms 12632 KB Output is correct
6 Correct 7 ms 12632 KB Output is correct
7 Correct 8 ms 12632 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 4 ms 12632 KB Output is correct
10 Correct 4 ms 12652 KB Output is correct
11 Correct 5 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 384 ms 111748 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -