ABC247D Cylinder Solution

更好的阅读体验戳此进入

题面

存在一个队列，给定 $q$$q$ 个操作或询问，按以下格式输入：

1 x c，表示向队尾插入 $c$$c$ 个 $x$$x$。

2 c，表示从队头取出 $c$$c$ 个元素并输出它们的和。

Solution

大概也算是个语法题？

维护一个队列，里面元素是个 pair < int, int > 记录元素值和数量，$1$$1$ 操作就是队尾插入一个 {x, c}，$2$$2$ 操作判断一下，如果队头能取就取出来然后求和，否则对队头做一个类似 ODT 的 Split 的操作，然后对应维护一下 $ans$$ans$ 即可。

对于 $2$$2$ 操作详细解释一下，不难想到维护询问剩余的 $c$$c$，令队头元素的 $c$$c$ 为 $c^{\prime }$$c'$，值为 $x$$x$，显然若 $c^{\prime }\le c$$c' \le c$，那么直接 $c\leftarrow c-c^{\prime }$$c \leftarrow c - c'$ 然后答案加上 $c^{\prime }\times x$$c' \times x$ 后把队头弹出，反之答案加上 $c\times x$$c \times x$ 并 $c^{\prime }\leftarrow c^{\prime }-c$$c' \leftarrow c' - c$，注意判断队列非空即可。

Code

xxxxxxxxxx
64
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
queue < pair < int, int >/*value, cnt*/ > balls;
27

28
int main(){
29
    int N = read();
30
    while(N--){
31
        int opt = read();
32
        if(opt == 1){
33
            int x = read(), c = read();
34
            balls.push({x, c});
35
        }else{
36
            ll ans(0);
37
            int c = read();
38
            while(c > 0 && !balls.empty()){
39
                auto tp = balls.front();
40
                if(c >= tp.second)balls.pop(), c -= tp.second, ans += (ll)tp.first * tp.second;
41
                else ans += (ll)c * tp.first, balls.front().second -= c, c = 0;
42
            }printf("%lld\n", ans);
43
        }
44
    }
45

46
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
47
    return 0;
48
}
49

50
template < typename T >
51
inline T read(void){
52
    T ret(0);
53
    short flag(1);
54
    char c = getchar();
55
    while(c != '-' && !isdigit(c))c = getchar();
56
    if(c == '-')flag = -1, c = getchar();
57
    while(isdigit(c)){
58
        ret *= 10;
59
        ret += int(c - '0');
60
        c = getchar();
61
    }
62
    ret *= flag;
63
    return ret;
64
}

UPD

update-2022_10_24 初稿