oj.uz

Submission #836923

# Submission time Handle Problem Language Result Execution time Memory
836923 2023-08-24T17:17:02 Z Abrar_Al_Samit Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 7592 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]; 
}

bool is[nax];
int max_towers(int L, int R, int D) {
	vector<int>H;
	for(int i=L; i<=R; ++i) {
		H.push_back(h[i]);
	}
	n = R-L+1;

	int mn = H[0];
  	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] - mn;
    		mn = 2e9;
    	} else {
    		mn = min(mn, H[i]);
    	}
  	}


  	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;
  	}

  	mn = H[n-1];
  	for(int i=n-2; i>0; --i) {
  		if(l_maxima[i]) {
  			r[i] = H[i] - mn;
  			mn = 2e9;
  		} else {
  			mn = min(mn, H[i]);
  		}
  	}



	int ret = 1;

	set<pair<int,int>>s;
	for(int i=1; i<n; ++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 Execution timed out 4006 ms 2340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '91', found: '68'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '91', found: '68'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4019 ms 7592 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 4090 ms 1568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '91', found: '68'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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