oj.uz

Submission #1079674

# Submission time Handle Problem Language Result Execution time Memory
1079674 2024-08-28T21:04:32 Z allin27x Radio Towers (IOI22_towers) C++17
14 / 100
 883 ms 22720 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;

vector<int> usef;
map<int,int> nxt;
map<int,int> prv;

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);
	for (int i=0; i<h.size(); i++) if (lc[i]!=-2) usef.push_back(i);
	for (int i=0; i<usef.size()-1; i++) nxt[usef[i]] = usef[i+1];
	for (int i=1; i<usef.size(); i++) prv[usef[i]] = usef[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 += nxt.count(l) && h[l] < h[nxt[l]] && nxt[l]<=r;
	s += prv.count(r) && h[r] < h[prv[r]] && prv[r]>=l;
	return s;
}

Compilation message

towers.cpp: In function 'long long int dfs(long long int, long long int)':
towers.cpp:36:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   36 |  if (!lans) return rans; if (!rans) return lans;
      |  ^~
towers.cpp:36:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   36 |  if (!lans) return rans; if (!rans) return lans;
      |                          ^~
towers.cpp: In function 'void init0(long long int)':
towers.cpp:72: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]
   72 |  for (int i=1; i<h.size(); i++) pr[i] = pr[i-1] + (lc[i]==-1 && rc[i]==-1);
      |                ~^~~~~~~~~
towers.cpp:73: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]
   73 |  for (int i=0; i<h.size(); i++) if (lc[i]!=-2) usef.push_back(i);
      |                ~^~~~~~~~~
towers.cpp:74: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]
   74 |  for (int i=0; i<usef.size()-1; i++) nxt[usef[i]] = usef[i+1];
      |                ~^~~~~~~~~~~~~~
towers.cpp:75: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]
   75 |  for (int i=1; i<usef.size(); i++) prv[usef[i]] = usef[i-1];
      |                ~^~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 343 ms 10904 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 600 KB Output is correct
3 Incorrect 1 ms 600 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 600 KB Output is correct
3 Incorrect 1 ms 600 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 675 ms 17680 KB Output is correct
2 Correct 848 ms 17956 KB Output is correct
3 Correct 843 ms 17848 KB Output is correct
4 Correct 882 ms 17848 KB Output is correct
5 Correct 882 ms 17848 KB Output is correct
6 Correct 847 ms 17876 KB Output is correct
7 Correct 843 ms 17848 KB Output is correct
8 Correct 883 ms 22712 KB Output is correct
9 Correct 793 ms 22712 KB Output is correct
10 Correct 875 ms 21352 KB Output is correct
11 Correct 881 ms 21516 KB Output is correct
12 Correct 853 ms 22712 KB Output is correct
13 Correct 841 ms 22712 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 1 ms 856 KB Output is correct
17 Correct 47 ms 18044 KB Output is correct
18 Correct 54 ms 17848 KB Output is correct
19 Correct 47 ms 17968 KB Output is correct
20 Correct 49 ms 22700 KB Output is correct
21 Correct 54 ms 22456 KB Output is correct
22 Correct 57 ms 18004 KB Output is correct
23 Correct 47 ms 17912 KB Output is correct
24 Correct 70 ms 17848 KB Output is correct
25 Correct 64 ms 22720 KB Output is correct
26 Correct 50 ms 22252 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 1 ms 856 KB Output is correct
31 Correct 1 ms 856 KB Output is correct
32 Correct 2 ms 600 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 1 ms 600 KB Output is correct
35 Correct 1 ms 856 KB Output is correct
36 Correct 1 ms 856 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 4312 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 600 KB Output is correct
3 Incorrect 1 ms 600 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 343 ms 10904 KB 2nd lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -