oj.uz

Submission #785384

# Submission time Handle Problem Language Result Execution time Memory
785384 2023-07-17T08:48:04 Z ono_de206 Radio Towers (IOI22_towers) C++17
0 / 100
 735 ms 23384 KB 
#include "towers.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

//#define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 1e5 + 10, inf = 2e9 + 10;
int h[mxn], n, lg[mxn], L[mxn], R[mxn], pre[mxn], pos;
pair<int, int> p[mxn][20];
bool sub1;

pair<int, int> get(int l, int r) {
	int k = lg[r - l + 1];
	return max(p[l][k], p[r - (1 << k) + 1][k]);
}

void build(int l, int r) {
	if(l > r) return;
	int pos = get(l, r).ss;
	L[pos] = l;
	R[pos] = r;
	if(l == r) return;
	pre[pos] = 1;
	build(l, pos - 1);
	build(pos + 1, r);
}

void init(int _n, vector<int> H) {
	n = _n;
	for(int i = 1; i <= n; i++) {
		h[i] = H[i - 1];
		p[i][0] = {h[i], i};
	}
	for(int j = 1; j < 20; j++) {
		for(int i = 1; i + (1 << j) - 1 <= n; i++) {
			p[i][j] = max(p[i][j - 1], p[i + (1 << (j - 1))][j - 1]);
		}
	}
	for(int i = 2; i <= n; i++) {
		lg[i] = lg[i / 2] + 1;
	}
	build(1, n);
	for(int i = 1; i <= n; i++) {
		pre[i] += pre[i - 1];
	}
	sub1 = 1;
	pos = get(1, n).ss;
	for(int i = 1; i <= n; i++) {
		if(L[i] < i && R[i] > i && (L[i] > 1 || R[i] < n)) sub1 = 0;
	}
}

int max_towers(int l, int r, int D) {
	l++;
	r++;
	if(l == r) return 1;
	if(sub1) {
		return (l < pos && r > pos && max(h[l], h[r]) <= h[pos] - D);
	}
	int ans = r - l + 1 - pre[r] + pre[l - 1];
	if(pre[l] - pre[l - 1] == 1 && R[l] == l) ans++;
	if(pre[r] - pre[r - 1] == 1 && L[r] == r) ans++;
	return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 13520 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
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: '16'
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: '16'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 18468 KB Output is correct
2 Correct 732 ms 18616 KB Output is correct
3 Correct 566 ms 18676 KB Output is correct
4 Correct 508 ms 18604 KB Output is correct
5 Correct 599 ms 18616 KB Output is correct
6 Correct 669 ms 18600 KB Output is correct
7 Correct 735 ms 18596 KB Output is correct
8 Incorrect 657 ms 23384 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 4688 KB 1st lines differ - on the 1st token, expected: '7197', found: '8004'
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: '16'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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