#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
vector<int> leaf, lt;
vector<vector<int>> spa, spa2, spa3;
vector<int> lp, rp;
vector<int> mn;
struct fenw{
int n;
vector<int> tr;
fenw(int m){
n = m + 4;
tr.resize(n, -1);
}
void push(int pos, int val){
for(int i = pos; i < n; i += (i & -i)){
tr[i] = max(tr[i], val);
}
}
int get(int pos){
int rv = -1;
for(int i = pos; i > 0; i -= (i & -i)){
rv = max(rv, tr[i]);
}
return rv;
}
};
int fir = 0;
void init(int N, std::vector<int> H) {
n = N;
a = H;
spa.resize(n, vector<int>(20, (int)1e9));
spa2.resize(n, vector<int>(20, (int)1e9));
spa3.resize(n, vector<int>(20, (int)1e9));
lp.resize(n);
rp.resize(n);
mn.resize(n, (int)1e9);
}
int max_towers(int L, int R, int D) {
if(!fir){
fir = 1;
vector<int> srt;
for(int i = 0; i < n; ++i){
srt.push_back(a[i]);
srt.push_back(a[i] + D);
}
sort(srt.begin(), srt.end());
srt.erase(unique(srt.begin(), srt.end()), srt.end());
auto getnum = [&](int x)->int{
return lower_bound(srt.begin(), srt.end(), x) - srt.begin();
};
auto getl = [&](vector<int> x)->vector<int>{
fenw tr((int)srt.size() + 4);
vector<int> rv(n);
for(int i = 0; i < n; ++i){
rv[i] = tr.get((int)srt.size() - getnum(a[i] + D)) + 1;
rv[i] = i - rv[i];
tr.push((int)srt.size() - getnum(a[i]), i);
}
return rv;
};
lp = getl(a);
reverse(a.begin(), a.end());
rp = getl(a);
reverse(a.begin(), a.end());
reverse(rp.begin(), rp.end());
// for(int i = 0; i < n; ++i){
// cout << i - lp[i] << ' ' << i + rp[i] << endl;
// }
// cout << endl;
for(int i = n - 1; i >= 0; --i){
spa[i][0] = i + rp[i];
for(int j = 1; j < 20; ++j){
if(spa[i][j - 1] < n - 1){
spa[i][j] = spa2[spa[i][j - 1] + 1][j - 1];
}
}
if(i + 1 < n){
for(int j = 0; j < 20; ++j){
spa[i][j] = min(spa[i][j], spa[i + 1][j]);
}
for(int j = 0; j < 20; ++j){
spa2[i][j] = min(spa2[i][j], spa2[i + 1][j]);
}
}
for(int j = 0; j < 20; ++j){
spa2[i - lp[i]][j] = min(spa2[i - lp[i]][j], spa[i][j]);
}
mn[i - lp[i]] = min(mn[i - lp[i]], i);
}
for(int i = n - 2; i >= 0; --i){
mn[i] = min(mn[i], mn[i + 1]);
}
}
int ans = 0;
int pos = L, f = 1;
for(int i = 19; i >= 0; --i){
if(f){
if(spa[pos][i] <= R){
ans += (1 << i);
pos = spa[pos][i] + 1;
}
f = 0;
}
else{
if(spa2[pos][i] <= R){
ans += (1 << i);
pos = spa2[pos][i] + 1;
}
}
}
if(!ans) ans = 1;
else{
if(pos <= R){
if(mn[pos] <= R){
++ans;
}
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
454 ms |
23896 KB |
12th lines differ - on the 1st token, expected: '2', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
3 ms |
1100 KB |
Output is correct |
3 |
Correct |
2 ms |
976 KB |
Output is correct |
4 |
Correct |
2 ms |
976 KB |
Output is correct |
5 |
Correct |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
3 ms |
976 KB |
Output is correct |
7 |
Incorrect |
2 ms |
976 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
3 ms |
1100 KB |
Output is correct |
3 |
Correct |
2 ms |
976 KB |
Output is correct |
4 |
Correct |
2 ms |
976 KB |
Output is correct |
5 |
Correct |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
3 ms |
976 KB |
Output is correct |
7 |
Incorrect |
2 ms |
976 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
945 ms |
39544 KB |
21st lines differ - on the 1st token, expected: '20816', found: '20815' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
288 ms |
9804 KB |
2nd lines differ - on the 1st token, expected: '7063', found: '7197' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
3 ms |
1100 KB |
Output is correct |
3 |
Correct |
2 ms |
976 KB |
Output is correct |
4 |
Correct |
2 ms |
976 KB |
Output is correct |
5 |
Correct |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
3 ms |
976 KB |
Output is correct |
7 |
Incorrect |
2 ms |
976 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
454 ms |
23896 KB |
12th lines differ - on the 1st token, expected: '2', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |