oj.uz

Submission #1079691

# Submission time Handle Problem Language Result Execution time Memory
1079691 2024-08-28T21:28:08 Z allin27x Radio Towers (IOI22_towers) C++17
14 / 100
 705 ms 12440 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 = 4e9;
	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 Runtime error 14 ms 12440 KB Execution killed with signal 11
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 477 ms 6084 KB Output is correct
2 Correct 645 ms 6336 KB Output is correct
3 Correct 654 ms 6336 KB Output is correct
4 Correct 695 ms 6080 KB Output is correct
5 Correct 705 ms 6080 KB Output is correct
6 Correct 686 ms 6080 KB Output is correct
7 Correct 631 ms 6080 KB Output is correct
8 Correct 654 ms 10944 KB Output is correct
9 Correct 655 ms 11712 KB Output is correct
10 Correct 621 ms 9664 KB Output is correct
11 Correct 690 ms 10432 KB Output is correct
12 Correct 650 ms 10944 KB Output is correct
13 Correct 677 ms 11712 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 14 ms 6080 KB Output is correct
18 Correct 12 ms 6288 KB Output is correct
19 Correct 12 ms 6336 KB Output is correct
20 Correct 15 ms 11712 KB Output is correct
21 Correct 16 ms 10648 KB Output is correct
22 Correct 21 ms 6080 KB Output is correct
23 Correct 12 ms 6080 KB Output is correct
24 Correct 12 ms 6336 KB Output is correct
25 Correct 14 ms 11712 KB Output is correct
26 Correct 14 ms 10420 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 1 ms 600 KB Output is correct
32 Correct 1 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 213 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 Runtime error 14 ms 12440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -