oj.uz

Submission #1079594

# Submission time Handle Problem Language Result Execution time Memory
1079594 2024-08-28T18:21:59 Z allin27x Radio Towers (IOI22_towers) C++17
14 / 100
 716 ms 12104 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5+4;
vector<int> h;
vector<int> lc,rc,a;
vector<int> ds;
int pr[N];

int sum (int l, int r) {
	if (l > r) return 0;
	if (r==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) return rans; if (!rans) return lans;
	ds.push_back(a[i] + min(lans, rans));

	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];
	helper(0, N-1, (int)1e18);
	sort(ds.begin(), ds.end());
	pr[0] = (lc[0]==-1 && rc[0]==-1);
	for (int i=1; i<N; i++) pr[i] = pr[i-1] + (lc[i]==-1 && rc[i]==-1);

}

signed max_towers(signed l, signed r, signed d) {
	if (r-l <= 1) return 1;
	int s = sum(l+1,r-1);
	s += h[l] < h[l+1]; s += h[r] < h[r-1];
	return s;
}

Compilation message

towers.cpp: In function 'long long int dfs(long long int, long long int)':
towers.cpp:24:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   24 |  if (!lans) return rans; if (!rans) return lans;
      |  ^~
towers.cpp:24:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |  if (!lans) return rans; if (!rans) return lans;
      |                          ^~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 308 ms 6276 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 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 5712 KB Output is correct
2 Correct 642 ms 5704 KB Output is correct
3 Correct 682 ms 5704 KB Output is correct
4 Correct 716 ms 5960 KB Output is correct
5 Correct 686 ms 5960 KB Output is correct
6 Correct 600 ms 5952 KB Output is correct
7 Correct 640 ms 5960 KB Output is correct
8 Correct 703 ms 11180 KB Output is correct
9 Correct 623 ms 12104 KB Output is correct
10 Correct 665 ms 9800 KB Output is correct
11 Correct 678 ms 10312 KB Output is correct
12 Correct 605 ms 11336 KB Output is correct
13 Correct 648 ms 12104 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 452 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 22 ms 5704 KB Output is correct
18 Correct 14 ms 5960 KB Output is correct
19 Correct 17 ms 5960 KB Output is correct
20 Correct 20 ms 12104 KB Output is correct
21 Correct 19 ms 11080 KB Output is correct
22 Correct 19 ms 5704 KB Output is correct
23 Correct 16 ms 5960 KB Output is correct
24 Correct 15 ms 5948 KB Output is correct
25 Correct 15 ms 12104 KB Output is correct
26 Correct 21 ms 10824 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 1 ms 356 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 1 ms 600 KB Output is correct
36 Correct 0 ms 600 KB Output is correct

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

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