oj.uz

Submission #1079693

# Submission time Handle Problem Language Result Execution time Memory
1079693 2024-08-28T21:29:27 Z allin27x Radio Towers (IOI22_towers) C++17
14 / 100
 689 ms 11712 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 1e5+4;
vector<int> h;
vector<int> lc,rc,a;
int pr[MAXN];
int inited = 0;

int fl[MAXN];
int fr[MAXN];

int sum (int l, int r) {
	if (l > r) return 0;
	if (l==0) return pr[r];
	return pr[r] - pr[l-1];
}

int dfs(int i, int d){
	if (i==-1) return 0;
	if (lc[i]==-1 && rc[i]==-1) return -a[i];
	int lans = dfs(lc[i],d);
	int rans = dfs(rc[i],d);
	if (lans < 0 && a[i] - d >= -lans) lans = 1;
	if (rans < 0 && a[i] - d >= -rans) rans = 1;
	if (lans < 0) {
		lc[lc[i]] = -2; rc[lc[i]] = -2;
		lc[i] = -1;
	}
	if (rans < 0) {
		lc[rc[i]] = -2; rc[rc[i]] = -2;
		rc[i] = -1;
	}
	if (!lans) return rans; if (!rans) return lans;
	if (lans < 0 && rans < 0) return max(lans,rans);
	if (lans < 0) return rans;
	if (rans < 0) return lans;
	return lans + rans;
}

signed helper(signed l, signed r, int d){
	int sz = r-l+1;
	a.assign(sz,0); for (int i=l; i<=r; i++) a[i-l] = h[i];

	a.push_back(3e9);
	stack<int> st; st.push(sz);
	lc.assign(sz+1,-1); rc.assign(sz+1,-1);

	for (int i=0; i<sz; i++){
		int last = -1;
		while (a[i] > a[st.top()]) {
			last=st.top();
			st.pop();
		}
		lc[i] = last;
		rc[st.top()]=i;
		st.push(i);
	}
	return dfs(sz,d);
}


void init(signed N, std::vector<signed> H){
	h.resize(N); for (int i = 0; i < N; i++) h[i] = H[i];
}

void init0(int d) {
	helper(0, h.size()-1, d);
	pr[0] = (lc[0]==-1 && rc[0]==-1);
	for (int i=1; i<h.size(); i++) pr[i] = pr[i-1] + (lc[i]==-1 && rc[i]==-1);
	int rs = 1e9;
	for (int i=h.size()-1; i>=0; i--) {
		if (lc[i]!=-2) rs = i;
		fl[i] = rs;
	}
	rs = -1;
	for (int i=0; i<h.size(); i++) {
		if (lc[i]!=-2) rs = i;
		fr[i] = rs;
	}
}


signed max_towers(signed l, signed r, signed d) {
	if (!inited) init0(d), inited = 1;
	l = fl[l]; r = fr[r];
	if (r-l <= 1) return 1;
	int s = sum(l+1,r-1);
	s += rc[l] == -1;
	s += lc[r] == -1;
	return s;
}

Compilation message

towers.cpp: In function 'long long int dfs(long long int, long long int)':
towers.cpp:35:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   35 |  if (!lans) return rans; if (!rans) return lans;
      |  ^~
towers.cpp:35:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   35 |  if (!lans) return rans; if (!rans) return lans;
      |                          ^~
towers.cpp: In function 'void init0(long long int)':
towers.cpp:71:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i=1; i<h.size(); i++) pr[i] = pr[i-1] + (lc[i]==-1 && rc[i]==-1);
      |                ~^~~~~~~~~
towers.cpp:78:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i=0; i<h.size(); i++) {
      |                ~^~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '91', found: '92'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '91', found: '92'
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 6092 KB Output is correct
2 Correct 664 ms 6080 KB Output is correct
3 Correct 679 ms 6080 KB Output is correct
4 Correct 564 ms 6080 KB Output is correct
5 Correct 555 ms 6268 KB Output is correct
6 Correct 528 ms 6308 KB Output is correct
7 Correct 520 ms 6176 KB Output is correct
8 Correct 578 ms 10784 KB Output is correct
9 Correct 613 ms 11712 KB Output is correct
10 Correct 663 ms 9664 KB Output is correct
11 Correct 689 ms 10432 KB Output is correct
12 Correct 651 ms 10944 KB Output is correct
13 Correct 653 ms 11712 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 13 ms 6320 KB Output is correct
18 Correct 13 ms 6320 KB Output is correct
19 Correct 12 ms 6080 KB Output is correct
20 Correct 15 ms 11712 KB Output is correct
21 Correct 18 ms 10940 KB Output is correct
22 Correct 13 ms 6316 KB Output is correct
23 Correct 13 ms 6080 KB Output is correct
24 Correct 12 ms 6080 KB Output is correct
25 Correct 14 ms 11712 KB Output is correct
26 Correct 16 ms 10432 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 0 ms 600 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 1 ms 600 KB Output is correct
36 Correct 1 ms 600 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 167 ms 1692 KB 2nd lines differ - on the 1st token, expected: '7063', found: '7197'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '91', found: '92'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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