oj.uz

Submission #1056505

# Submission time Handle Problem Language Result Execution time Memory
1056505 2024-08-13T09:49:33 Z AmirAli_H1 Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 4048 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;

typedef			long long				ll;
typedef			pair<int, int>			pii;
typedef			pair<ll, ll>			pll;

#define			F						first
#define			S						second
#define			all(x)					(x).begin(),(x).end()
#define			len(x)					((ll) (x).size())
#define			Mp						make_pair
#define			pb						push_back
#define			endl					'\n'
#define			sep						' '

const int oo = 1e9 + 7;
const int maxn = 1e5 + 7;

int n;
ll A[maxn]; int M[maxn], Mx[maxn];
vector<int> ls, lsx; int val[maxn];

void init(int N, vector<int> H) {
	n = N;
	for (int i = 0; i < n; i++) A[i] = H[i];
	
	for (int i = 0; i < n; i++) {
		val[i] = 0;
		if ((i - 1 >= 0 && A[i] > A[i - 1]) && (i + 1 < n && A[i] > A[i + 1])) {
			M[i] = 1; Mx[i] = 1;
		}
		else if ((i - 1 >= 0 && A[i] < A[i - 1]) && (i + 1 < n && A[i] < A[i + 1])) {
			M[i] = 1; Mx[i] = -1;
		}
		if (M[i]) ls.pb(i);
	}
	
	while (len(ls) > 1) {
		ll mn = oo;
		for (int j = 1; j < len(ls); j++) {
			int j1 = ls[j - 1], j2 = ls[j];
			mn = min(mn, abs(A[j1] - A[j2]));
		}
		for (int j = 1; j < len(ls); j++) {
			int j1 = ls[j - 1], j2 = ls[j];
			if (abs(A[j1] - A[j2]) == mn) {
				M[j1] = 0; M[j2] = 0;
				val[j1] = mn; val[j2] = mn;
			}
		}
		lsx.clear();
		for (int j : ls) {
			if (M[j]) lsx.pb(j);
		}
		ls = lsx;
	}
	val[ls[0]] = oo;
}

int get_min(int L, int R) {
	ll mn = oo;
	for (int j = L; j <= R; j++) mn = min(mn, A[j]);
	return mn;
}

int max_towers(int L, int R, int D) {
	int lx = R + 1, rx = L - 1;
	
	lsx.clear();
	for (int j = L; j <= R; j++) {
		if (val[j] >= D) {
			lx = min(lx, j); rx = max(rx, j);
			lsx.pb(j);
		}
	}
	if (len(lsx) <= 1) return 1;
	
	int t = len(lsx) / 2;
	if (Mx[lsx[0]] == -1 && Mx[lsx.back()] == -1) t++;
	
	if (Mx[lsx[0]] == 1 && get_min(L, lx - 1) <= A[lsx[0]] - D) t++;
	if (Mx[lsx.back()] == 1 && get_min(rx + 1, R) <= A[lsx.back()] - D) t++;
	return t;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1335 ms 1624 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 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 3 ms 532 KB Output is correct
8 Runtime error 0 ms 600 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 3 ms 532 KB Output is correct
8 Runtime error 0 ms 600 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2554 ms 1280 KB Output is correct
2 Execution timed out 4018 ms 4048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 3 ms 532 KB Output is correct
8 Runtime error 0 ms 600 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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