Star's Blog

1
#include <iostream>
2
#include <queue>
3
#define int long long
4

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 200010;
9
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q1, q2;
10

11
signed main() {
12
    int q;
13
    LL zcnt = 0, s1 = 0, s2 = 0;
14
    scanf("%lld", &q);
15
    while (q--) {
16
        int op;
17
        scanf("%lld", &op);
18
        if (op == 1) {
19
            int x, y;
20
            scanf("%lld%lld", &x, &y);
21
            if (y == 0) zcnt += x;
22
            else if (y > 0) q1.emplace(y, x), s1 += x;
23
            else q2.emplace(-y, x), s2 += x;
24
        }
25
        else {
26
            int k;
27
            scanf("%lld", &k);
28
            if (op == 2) {
29
                if (s1 >= k) {
30
                    printf("0\n");
31
                    continue;
32
                }
33
                k -= s1;
34
                if (k <= zcnt) {
35
                    pair<int, int> t;
36
                    if (!q1.empty() && q1.top().first == 1) t = q1.top(), q1.pop();
37
                    else t = {1, 0};
38
                    s1 += k;
39
                    t.second += k;
40
                    q1.push(t);
41
                    printf("%lld\n", k);
42
                }
43
                else {
44
                    pair<int, int> t;
45
                    if (!q1.empty() && q1.top().first == 1) t = q1.top(), q1.pop();
46
                    else t = {1, 0};
47
                    t.second += k;
48
                    s1 += k;
49
                    q1.push(t);
50

51
                    k -= zcnt;
52
                    // printf("%lld\n", k);
53
                    LL res = zcnt;
54
                    while (k && k >= q2.top().second) {
55
                        k -= q2.top().second;
56
                        res += (LL)(q2.top().first + 1) * q2.top().second;
57
                        s2 -= q2.top().second;
58
                        q2.pop();
59
                    }
60
                    if (k) {
61
                        auto t = q2.top();
62
                        q2.pop();
63
                        t.second -= k;
64
                        s2 -= k;
65
                        res += (LL)(t.first + 1) * k;
66
                        q2.push(t);
67
                    }
68
                    printf("%lld\n", res);
69
                    zcnt = 0;
70
                }
71
            }
72
            else {
73
                if (s2 >= k) {
74
                    printf("0\n");
75
                    continue;
76
                }
77
                k -= s2;
78
                if (k <= zcnt) {
79
                    pair<int, int> t;
80
                    if (!q2.empty() && q2.top().first == 1) t = q2.top(), q2.pop();
81
                    else t = {1, 0};
82
                    s2 += k;
83
                    t.second += k;
84
                    q2.push(t);
85
                    printf("%lld\n", k);
86
                }
87
                else {
88
                    pair<int, int> t;
89
                    if (!q2.empty() && q2.top().first == 1) t = q2.top(), q2.pop();
90
                    else t = {1, 0};
91
                    t.second += k;
92
                    s2 += k;
93
                    q2.push(t);
94

95
                    k -= zcnt;
96
                    LL res = 0;
97
                    while (k && k >= q1.top().second) {
98
                        k -= q1.top().second;
99
                        res += (LL)(q1.top().first + 1) * q1.top().second;
100
                        s1 -= q1.top().second;
101
                        q1.pop();
102
                    }
103
                    if (k) {
104
                        auto t = q1.top();
105
                        q1.pop();
106
                        t.second -= k;
107
                        res += (LL)(t.first + 1) * k;
108
                        s1 -= k;
109
                        q1.push(t);
110
                    }
111
                    printf("%lld\n", res);
112
                    zcnt = 0;
113
                }
114
            }
115
        }
116
    }
117
    return 0;
118
}

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 100010;
7

8
int ver[N * 2], ne[N * 2], head[N], tot, t;
9
bool vis[N];
10

11
void add(int x, int y) {
12
    ver[++tot] = y;
13
    ne[tot] = head[x];
14
    head[x] = tot;
15
}
16

17
void dfs(int x) {
18
    if (vis[x]) return;
19
    vis[x] = true;
20
    t++;
21
    for (int i = head[x]; i; i = ne[i]) {
22
        int y = ver[i];
23
        dfs(y);
24
    }
25
}
26

27
int main() {
28
    int T;
29
    scanf("%d", &T);
30
    while (T--) {
31
        int n, c2 = 0;
32
        scanf("%d", &n);
33
        tot = 0;
34
        memset(head, 0, sizeof(int) * (n + 1));
35
        memset(vis, 0, sizeof(bool) * (n + 1));
36
        for (int i = 1; i <= n; ++i) {
37
            int t;
38
            scanf("%d", &t);
39
            c2 += t == 2;
40
        }
41
        for (int i = 1; i <= c2; ++i) {
42
            add(i, (i + 1) % n + 1);
43
            add((i + 1) % n + 1, i);
44
        }
45
        for (int i = c2 + 1; i <= n; ++i) {
46
            add(i, (i + 2) % n + 1);
47
            add((i + 2) % n + 1, i);
48
        }
49
        t = 0;
50
        dfs(1);
51
        if (t == n) printf("Yes\n");
52
        else printf("No\n");
53
    }
54
    return 0;
55
}