#include <bits/stdc++.h>
#include "routers.h"
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
using namespace std;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;
const int MAX = 100010;
int arr[MAX], fir[MAX], cnt[MAX], res[MAX];
int lowerBound(int lo, int hi, int tar) { // tar + 1반환
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
int chk = use_detector(mid);
if (chk < tar) lo = mid;
else hi = mid;
}
return hi;
}
void divide(int lo, int hi) {
int mid = (lo + hi) / 2;
int tar = use_detector(mid);
int lft = lowerBound(lo, hi, tar);
int rgt = lowerBound(lo, hi, tar + 1) - 1;
arr[lft] = tar;
arr[rgt] = tar;
if (lo + 1 < lft) divide(lo, lft - 1);
if (rgt + 1 < hi) divide(rgt, hi);
}
std::vector<int> find_routers(int l, int n, int q) {
for (int i = 0; i < MAX; i++) arr[i] = -1;
divide(-1, l + 1);
for (int i = 1; i < l; i++) arr[i] = max(arr[i], arr[i - 1]);
for (int i = 0; i < l + 1; i++) {
if (arr[i] >= 0) cnt[arr[i]]++;
if (i >= 1 && arr[i] > arr[i - 1]) fir[arr[i]] = i;
}
fir[0] = 0;
res[0] = 0;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] + (cnt[i - 1] - 1) * 2;
cnt[i] -= cnt[i - 1] - 2;
}
vector<int> v;
for (int i = 0; i < n; i++) v.push_back(res[i]);
return v;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
856 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
832 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
604 KB |
Too many queries used |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
2 ms |
860 KB |
Partial score |
2 |
Partially correct |
2 ms |
860 KB |
Partial score |
3 |
Partially correct |
2 ms |
860 KB |
Partial score |
4 |
Partially correct |
2 ms |
860 KB |
Partial score |
5 |
Partially correct |
2 ms |
856 KB |
Partial score |
6 |
Partially correct |
2 ms |
860 KB |
Partial score |
7 |
Partially correct |
2 ms |
860 KB |
Partial score |
8 |
Partially correct |
2 ms |
860 KB |
Partial score |
9 |
Partially correct |
2 ms |
860 KB |
Partial score |
10 |
Partially correct |
2 ms |
860 KB |
Partial score |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Partially correct |
2 ms |
860 KB |
Partial score |
13 |
Correct |
1 ms |
860 KB |
Output is correct |
14 |
Partially correct |
2 ms |
860 KB |
Partial score |
15 |
Partially correct |
2 ms |
860 KB |
Partial score |
16 |
Partially correct |
2 ms |
860 KB |
Partial score |
17 |
Partially correct |
2 ms |
860 KB |
Partial score |
18 |
Partially correct |
2 ms |
860 KB |
Partial score |
19 |
Partially correct |
2 ms |
860 KB |
Partial score |
20 |
Partially correct |
2 ms |
860 KB |
Partial score |
21 |
Partially correct |
2 ms |
860 KB |
Partial score |