NC16430（蚯蚓 ）

感受


思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 7e6 + 10;
struct node{
    int dfn;
    ll x;
};
int m, q;
int n, u, v, t, now;
ll ans1[maxn], ans2[maxn], a[maxn];
queue<node> que[5];
ll solve(){
    int id = -1; ll val, tmp;
    if(!que[1].empty()){
        auto itm = que[1].front();
        tmp = (ll)1 * (now - itm.dfn) * q + itm.x;
        if(id < 0){
            id = 1; val = tmp;
        }
    }
    if(!que[2].empty()){
        auto itm = que[2].front();
        tmp = (ll)1 * (now - itm.dfn) * q + itm.x;
        if(id < 0 || tmp > val){
            id = 2; val = tmp;
        }
    }
    if(!que[3].empty()){
        auto itm = que[3].front();
        tmp = (ll)1 * (now - itm.dfn) * q + itm.x;
        if(id < 0 || tmp > val){
            id = 3; val = tmp;
        }
    }
    ll x1 = val * u / v, x2; x2 = val - x1;
    if(x1 < x2) swap(x1, x2);
    que[2].push((node){now + 1, x1}); que[3].push((node){now + 1, x2});
    que[id].pop();
    return val;
}
ll solve1(){
    int id = -1; ll val, tmp;
    if(!que[1].empty()){
        auto itm = que[1].front();
        tmp = (ll)1 * (now - itm.dfn) * q + itm.x;
        if(id < 0){
            id = 1; val = tmp;
        }
    }
    if(!que[2].empty()){
        auto itm = que[2].front();
        tmp = (ll)1 * (now - itm.dfn) * q + itm.x;
        if(id < 0 || tmp > val){
            id = 2; val = tmp;
        }
    }
    if(!que[3].empty()){
        auto itm = que[3].front();
        tmp = (ll)1 * (now - itm.dfn) * q + itm.x;
        if(id < 0 || tmp > val){
            id = 3; val = tmp;
        }
    }
    que[id].pop();
    return val;
}
int main(){
    scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    sort(a + 1, a + n + 1);
    for(int i = n; i >= 1; i--){
        que[1].push((node){1, a[i]});
    }
    for(now = 1; now <= m; now++){
        ans1[now] = solve();
    }
    for(int i = 1; i <= n + m; i++){
        ans2[i] = solve1();
    }
    for(int i = t; i <= m; i += t){
        printf("%lld ", ans1[i]);
    }
    putchar('\n');
    for(int i = t; i <= n + m; i += t){
        printf("%lld ", ans2[i]);
    }
    putchar('\n');
    return 0;
}