QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#703080 | #5417. Chat Program | ZhZlzc | TL | 0ms | 3644kb | C++20 | 2.9kb | 2024-11-02 17:07:19 | 2024-11-02 17:07:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
// The 2022 ICPC Asia Nanjing Regional Contest
const int N = 200010;
int cnt = 0; // 标记新节点
int root[N];
struct{
int L, R, sum;
}tr[N << 5];
// [l, r]代表权值区间
int update(int pre, int l, int r, int x){
int rt = ++cnt;
tr[rt] = tr[pre];
tr[rt].sum++;
int mid = l + r >> 1;
if(l < r){
if(x <= mid){
tr[rt].L = update(tr[pre].L, l, mid, x);
}else{
tr[rt].R = update(tr[pre].R, mid + 1, r, x);
}
}
return rt;
}
// 查询存在多少个元素 <= k.
int query(int u, int v, int l, int r, int k){
if(l == r) return tr[u].sum - tr[v].sum;
int mid = l + r >> 1, res = 0;
if(k <= mid){
res = query(tr[u].L, tr[v].L, l, mid, k);
}else{
res = tr[tr[u].L].sum - tr[tr[v].L].sum + query(tr[u].R, tr[v].R, mid + 1, r, k);
}
return res;
}
void sol(){
int n, k, m, c, d;
std::cin>>n>>k>>m>>c>>d;
int need = n - k + 1;
std::vector<i64>X;
std::vector<int>a(n + 1);
std::vector<i64>b(n + 1);
for(int i = 1;i<=n;i++){
std::cin>>a[i];
b[i] = a[i] + 1LL * i * d + c;
X.push_back(b[i]);
}
std::sort(X.begin(), X.end());
X.erase(std::unique(X.begin(), X.end()), X.end());
std::vector<int>iv(n + 1);
for(int i = 1;i<=n;i++){
iv[i] = std::upper_bound(X.begin(), X.end(), b[i]) - X.begin();
}
int mn = X.size();
for(int i = 1;i<=n;i++){
root[i] = update(root[i - 1], 1, mn, iv[i]);
}
std::vector<int>se;
for(int i = m + 1;i<=n;i++){
se.insert(std::lower_bound(se.begin(), se.end(), a[i]), a[i]);
}
auto calc = [&](i64 tar, int kk, int i)->int{
int res = std::upper_bound(se.begin(), se.end(), tar) - se.begin();
if(kk){
res += query(root[i + m - 1], root[i - 1], 1, mn, kk);
}
return res;
};
i64 ans = 0;
for(int i = 1;i + m - 1<=n;i++){
// 在可持久化线段树中查询的段为:[i, i + m - 1]
i64 l = ans - 1, r = X.back() + 1;
while(l + 1 != r){
i64 tar = l + r >> 1;
i64 tarr = tar + 1LL * i * d;
int kk = std::upper_bound(X.begin(), X.end(), tarr) - X.begin();
int N = calc(tar, kk, i);
if(N >= need) r = tar; else l = tar;
}
if(r != X.back() + 1){
ans = std::max(ans, r);
}
if(i + m <= n){
se.erase(std::lower_bound(se.begin(), se.end(), a[i + m]));
}
se.insert(std::lower_bound(se.begin(), se.end(), a[i]), a[i]);
}
std::cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
int t = 1;
while(t--) sol();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
input:
6 4 3 1 2 1 1 4 5 1 4
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
7 3 2 4 0 1 9 1 9 8 1 0
output:
9
result:
ok 1 number(s): "9"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
8 3 5 0 0 2 0 2 2 1 2 1 8
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: -100
Time Limit Exceeded
input:
200000 200000 100000 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...