QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#703080#5417. Chat ProgramZhZlzcTL 0ms3644kbC++202.9kb2024-11-02 17:07:192024-11-02 17:07:20

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 17:07:20]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3644kb
  • [2024-11-02 17:07:19]
  • 提交

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 ...

output:


result: