oj.uz

Submission #1077289

# Submission time Handle Problem Language Result Execution time Memory
1077289 2024-08-27T04:43:42 Z pcc Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 12212 KB 
#include "towers.h"

#include <vector>
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fs first
#define sc second
using namespace std;

const int B = 20;
const int mxn = 1e5+10;
const int inf = 1e9;

int mx;
int N;
vector<int> H;

int par[mxn][B];
pii tree[mxn];
int arr[mxn];
int rt;
int dep[mxn];
pii big[mxn];
pii eul[mxn];
int dp[mxn];

void dfs(int now){
	for(int i = 1;i<B;i++)par[now][i] = par[par[now][i-1]][i-1];
	eul[now] = pii(now,now);
	if(tree[now].fs){
		int nxt = tree[now].fs;
		assert(arr[now]>arr[nxt]);
		dep[nxt] = dep[now]+1;
		par[nxt][0] = now;
		dfs(nxt);
		eul[now].fs = eul[nxt].fs;
	}
	if(tree[now].sc){
		int nxt = tree[now].sc;
		assert(arr[now]>arr[nxt]);
		dep[nxt] = dep[now]+1;
		par[nxt][0] = now;
		dfs(nxt);
		eul[now].sc = eul[nxt].sc;
	}
	return;
}

void add(int now,int val,int D){
	int pos = now;
	int tar = arr[now]+D;
	for(int i = B-1;i>=0;i--){
		int p = par[now][i];
		if(arr[p]<tar)now = p;
	}
	if(arr[now]<tar)now = par[now][0];
	if(arr[now]<tar)return;
	int side = 0;
	int rs = tree[now].sc;
	if(rs&&eul[rs].fs<=pos&&eul[rs].sc>=pos)side = 1;
	if(!side)big[now].fs = max(big[now].fs,val);
	else big[now].sc = max(big[now].sc,val);
	return;
}

int dfs1(int now,int D){
	big[now].fs = big[now].sc = 0;
	dp[now] = 1;
	if(tree[now].fs){
		int nxt = tree[now].fs;
		big[now].fs = max({big[nxt].fs,big[nxt].sc,big[now].fs});
		dp[now] = max(dp[now],dfs1(tree[now].fs,D));
	}
	if(tree[now].sc){
		int nxt = tree[now].fs;
		big[now].sc = max({big[nxt].fs,big[nxt].sc,big[now].sc});
		dp[now] = max(dp[now],dfs1(tree[now].sc,D));
	}
	dp[now] = max(dp[now],big[now].fs+big[now].sc);
	add(now,dp[now],D);
	return dp[now];
}

void build(int s,int e){
	for(auto &i:tree)i = pii(0,0);
	vector<int> st;
	for(int i = s;i<=e;i++){
		while(!st.empty()&&arr[st.back()]<arr[i]){
			tree[i].fs = st.back();
			st.pop_back();
		}
		if(!st.empty())tree[st.back()].sc = i;
		st.push_back(i);
	}
	rt = st[0];
	par[rt][0] = rt;
	dfs(rt);
}

void init(int NN, std::vector<int> HH) {
	N = NN;
	arr[0] = inf;
	for(int i = 0;i<N;i++)arr[i+1] = HH[i];
}

int max_towers(int L, int R, int D) {
	L++,R++;
	build(L,R);
	return dfs1(rt,D);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4003 ms 10684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB 1st lines differ - on the 1st token, expected: '13', found: '10'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB 1st lines differ - on the 1st token, expected: '13', found: '10'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4097 ms 12212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4038 ms 3928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB 1st lines differ - on the 1st token, expected: '13', found: '10'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4003 ms 10684 KB Time limit exceeded
2 Halted 0 ms 0 KB -