oj.uz

Submission #1079613

# Submission time Handle Problem Language Result Execution time Memory
1079613 2024-08-28T18:46:22 Z allin27x Radio Towers (IOI22_towers) C++17
14 / 100
 857 ms 22712 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(h[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 += h[l] < nxt[h[l]]; s += h[r] < prv[h[r]];
	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(h[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 341 ms 12004 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 2 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 2 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 666 ms 17852 KB Output is correct
2 Correct 804 ms 17848 KB Output is correct
3 Correct 835 ms 18012 KB Output is correct
4 Correct 804 ms 17848 KB Output is correct
5 Correct 857 ms 17848 KB Output is correct
6 Correct 828 ms 17848 KB Output is correct
7 Correct 827 ms 17836 KB Output is correct
8 Correct 757 ms 22712 KB Output is correct
9 Correct 791 ms 22712 KB Output is correct
10 Correct 757 ms 21432 KB Output is correct
11 Correct 846 ms 21428 KB Output is correct
12 Correct 780 ms 22704 KB Output is correct
13 Correct 780 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 77 ms 17848 KB Output is correct
18 Correct 74 ms 17948 KB Output is correct
19 Correct 78 ms 17848 KB Output is correct
20 Correct 46 ms 22552 KB Output is correct
21 Correct 45 ms 22456 KB Output is correct
22 Correct 74 ms 17848 KB Output is correct
23 Correct 74 ms 17892 KB Output is correct
24 Correct 76 ms 17848 KB Output is correct
25 Correct 48 ms 22712 KB Output is correct
26 Correct 49 ms 22200 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 1 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 224 ms 4308 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 2 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 341 ms 12004 KB 2nd lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -