$AcWing$ $133.$ 蚯蚓

假如有两只蚯蚓$x,y,(len(x) > len(y))$,则$x$一定会比$y$先切

设$x$切出的两只为$x_1,x_2$,设$t$秒($t > 0$)后切$y$,切出$y_1,y_2$

$x_1,x_2,y_1,y_2$增量相同(都加了$q*t$),所以$len(x_1) > len(y_1),len(x2) > len(y2)$

本身就具有单调性

所以维护三个队列,分别保存原来的,第一种方式切出的,第二种方式切出的

注意开$long \;long$

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
typedef long long ll;
#define int ll
using namespace std;

template <typename T>void in(T &x) {
    x = 0; T f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {x = 10*x + ch - '0'; ch = getchar();}
    x *= f;
}

template <typename T>void out(T x) {
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) out(x/10);
    putchar(x%10+'0');
}

//---------------------------------------------------------------

const int N = 1e5+7,M = 7e6+7;

int n,m,L,u,v,t;

bool cmp(const int &a,const int &b) {
    return a > b;
}

struct queue {
    int v[M];int hd,tl;
    void init() {hd = 1,tl = 0;}
    void I(int x) {v[++tl] = x;}
    int front() {return v[hd];}
    void P() {++hd;}
    bool empty() {return hd > tl;}
}q[3];

int find(int x,int y) {
    if(q[x].empty() && q[y].empty()) return 0;
    if(!q[x].empty() && q[y].empty()) return x;
    if(q[x].empty() && !q[y].empty()) return y;
    return (q[x].front() >= q[y].front()) ? x : y;
}
#undef int
int main() {
#define int ll
    int i,x,id;
    for(i = 0;i < 3; ++i) q[i].init();
    in(n); in(m); in(L); in(u); in(v); in(t);
    for(i = 1;i <= n; ++i) in(x),q[0].I(x);
    sort(q[0].v+1,q[0].v+n+1,cmp);
    for(i = 1;i <= m; ++i) {
        id = find(0,1); id = find(id,2);
        int len = q[id].front(); q[id].P();
        len += (i-1)*L;
        if(!(i%t)) out(len),putchar(' ');
        int len1 = (1ll*len*u)/v,len2 = len-len1;
        q[1].I(len1-i*L); q[2].I(len2-i*L);
    }
    putchar('\n');
    for(int i = 1;i <= n+m; ++i) {
        id = find(0,1); id = find(id,2);
        int len = q[id].front(); q[id].P();
        len += m*L;
        if(!(i%t)) out(len),putchar(' ');
    }
    return 0;
}