oj.uz

Submission #836880

# Submission time Handle Problem Language Result Execution time Memory
836880 2023-08-24T16:45:10 Z Abrar_Al_Samit Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 4348 KB 
#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

//subtask 2 & 3

const int nax = 100005;
int n;
bool l_maxima[nax];
int l[nax], r[nax];
int h[nax];
int pmax[nax], nmax[nax];

void init(int N, vector<int> H) {
  n = N;

  for(int i=0; i<n; ++i) h[i] = H[i];
  for(int i=1; i<n-1; ++i) {
    if(H[i]>H[i-1] && H[i]>H[i+1]) {
    	l_maxima[i] = 1;
    	l[i] = H[i] - H[i-1];
    	r[i] = H[i] - H[i+1];
    }
  }

  int p = -1;
  for(int i=1; i<n; ++i) if(l_maxima[i]) {
  	pmax[i] = p;
  	p = i;
  }
  p = n;
  for(int i=n-1; i>0; --i) if(l_maxima[i]) {
  	nmax[i] = p;
  	p = i;
  }
}

bool is[nax];
int max_towers(int L, int R, int D) {
	int ret = 1;

	set<pair<int,int>>s;
	for(int i=L+1; i<R; ++i) if(l_maxima[i]) {
		s.insert(make_pair(min(l[i], r[i]), i));
		is[i] = 1;
	}

	while(!s.empty() && s.begin()->first<D) {
		auto [x, i] = *s.begin();
		s.erase(s.begin());
		is[i] = 0;

		int lmin = h[i] - l[i], rmin = h[i] - r[i];

		if(pmax[i]!=-1 && is[pmax[i]]) {
			s.erase(make_pair(min(l[pmax[i]], r[pmax[i]]), pmax[i]));
			r[pmax[i]] = max(r[pmax[i]], h[pmax[i]] - rmin);
			s.insert(make_pair(min(l[pmax[i]], r[pmax[i]]), pmax[i]));
		}
		if(nmax[i]!=n && is[nmax[i]]) {
			s.erase(make_pair(min(l[nmax[i]], r[nmax[i]]), nmax[i]));
			l[nmax[i]] = max(l[nmax[i]], h[nmax[i]] - lmin);
			s.insert(make_pair(min(l[nmax[i]], r[nmax[i]]), nmax[i]));
		}
	} 
	ret = max(ret, (int)s.size() + 1);
	return ret;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 894 ms 976 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '12'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '12'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4066 ms 4348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4065 ms 1232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '12'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 894 ms 976 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -