oj.uz

답안 #1056515

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1056515 2024-08-13T09:51:35 Z AmirAli_H1 송신탑 (IOI22_towers) C++17
0 / 100
 4000 ms 4560 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 ll oo = 1e9 + 7;
const int maxn = 1e5 + 7;

int n;
ll A[maxn]; int M[maxn], Mx[maxn];
vector<int> ls, lsx; ll 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;
	}
	if (len(ls) >= 1) 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1139 ms 2904 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 4 ms 2392 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 3 ms 2392 KB Output is correct
7 Correct 3 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 0 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Incorrect 0 ms 2392 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 4 ms 2392 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 3 ms 2392 KB Output is correct
7 Correct 3 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 0 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Incorrect 0 ms 2392 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4077 ms 4560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2535 ms 3156 KB Output is correct
2 Execution timed out 4097 ms 4560 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 4 ms 2392 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 3 ms 2392 KB Output is correct
7 Correct 3 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 0 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Incorrect 0 ms 2392 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1139 ms 2904 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -