oj.uz

Submission #1079680

# Submission time Handle Problem Language Result Execution time Memory
1079680 2024-08-28T21:07:47 Z allin27x Radio Towers (IOI22_towers) C++17
14 / 100
 679 ms 10224 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 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 < 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);
}

signed max_towers(signed l, signed r, signed d) {
	if (!inited) init0(d), inited = 1;
	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:32:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   32 |  if (!lans) return rans; if (!rans) return lans;
      |  ^~
towers.cpp:32:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   32 |  if (!lans) return rans; if (!rans) return lans;
      |                          ^~
towers.cpp: In function 'void init0(long long int)':
towers.cpp:68: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]
   68 |  for (int i=1; i<h.size(); i++) pr[i] = pr[i-1] + (lc[i]==-1 && rc[i]==-1);
      |                ~^~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 5272 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 0 ms 340 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 0 ms 340 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 448 ms 4552 KB Output is correct
2 Correct 647 ms 4544 KB Output is correct
3 Correct 637 ms 4544 KB Output is correct
4 Correct 679 ms 4544 KB Output is correct
5 Correct 648 ms 4544 KB Output is correct
6 Correct 637 ms 4544 KB Output is correct
7 Correct 658 ms 4544 KB Output is correct
8 Correct 615 ms 9408 KB Output is correct
9 Correct 634 ms 10176 KB Output is correct
10 Correct 660 ms 8128 KB Output is correct
11 Correct 598 ms 8896 KB Output is correct
12 Correct 667 ms 9408 KB Output is correct
13 Correct 565 ms 10176 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 12 ms 4520 KB Output is correct
18 Correct 18 ms 4544 KB Output is correct
19 Correct 11 ms 4748 KB Output is correct
20 Correct 15 ms 10224 KB Output is correct
21 Correct 14 ms 9152 KB Output is correct
22 Correct 14 ms 4544 KB Output is correct
23 Correct 16 ms 4544 KB Output is correct
24 Correct 11 ms 4636 KB Output is correct
25 Correct 17 ms 10176 KB Output is correct
26 Correct 14 ms 8884 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 344 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 0 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 175 ms 1436 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 0 ms 340 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 283 ms 5272 KB 2nd lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -