oj.uz

Submission #1079614

# Submission time Handle Problem Language Result Execution time Memory
1079614 2024-08-28T18:48:28 Z allin27x Radio Towers (IOI22_towers) C++17
14 / 100
 873 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 += nxt.count(h[l]) && h[l] < nxt[h[l]]; s += prv.count(h[r]) && 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 366 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 716 ms 17840 KB Output is correct
2 Correct 814 ms 17832 KB Output is correct
3 Correct 857 ms 17992 KB Output is correct
4 Correct 863 ms 17896 KB Output is correct
5 Correct 815 ms 18056 KB Output is correct
6 Correct 873 ms 17848 KB Output is correct
7 Correct 850 ms 17848 KB Output is correct
8 Correct 770 ms 22712 KB Output is correct
9 Correct 832 ms 22584 KB Output is correct
10 Correct 803 ms 21556 KB Output is correct
11 Correct 800 ms 21432 KB Output is correct
12 Correct 815 ms 22712 KB Output is correct
13 Correct 805 ms 22568 KB Output is correct
14 Correct 1 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 81 ms 18068 KB Output is correct
18 Correct 78 ms 17848 KB Output is correct
19 Correct 73 ms 17848 KB Output is correct
20 Correct 49 ms 22712 KB Output is correct
21 Correct 50 ms 22456 KB Output is correct
22 Correct 81 ms 17812 KB Output is correct
23 Correct 73 ms 17848 KB Output is correct
24 Correct 77 ms 17848 KB Output is correct
25 Correct 45 ms 22712 KB Output is correct
26 Correct 45 ms 22068 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 2 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 211 ms 4316 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 366 ms 10904 KB 2nd lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -