长春寒假集训模拟赛 Ⅱ

2016.01.22 20:38 Fri| 24 visits oi_2016| 2016_竞赛日常| Text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int test, n, m, tot1, tot2, tot3, sum;
int v1[N], v2[N], v3[N];
pair<int, int> ans;

void solve1()
{
    int t = m, re = 0;
    t -= v1[1], ++re;
    tot3 = 0;
    for (int i = 2; i <= tot1; ++i)
        v3[++tot3] = v1[i];
    for (int i = 1; i <= tot2; ++i)
        v3[++tot3] = v2[i];
    sort(v3 + 1, v3 + tot3 + 1);
    if (tot3 <= sum) re += tot3;
    else
    {
        tot3 -= sum, re += sum;
        for (int i = 1; i <= tot3; ++i)
            if (t >= v3[i]) t -= v3[i], ++re;
            else break;
    }
    ans = max(ans, make_pair(re, t));
}

void solve2()
{
    int t = m, re = 0;
    for (int i = 1; i <= tot2; ++i)
        if (t >= v2[i]) t -= v2[i], ++re;
        else break;
    ans = max(ans, make_pair(re, t));
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    freopen("assassin.in", "r", stdin);
    freopen("assassin.out", "w", stdout);
    cin >> test;
    while (test--)
    {
        cin >> n >> m;
        tot1 = tot2 = sum = 0; ans = make_pair(0, 0);
        for (int x, y, i = 1; i <= n; ++i)
            x = read(), sum += (y = read()),
            (y ? v1[++tot1] : v2[++tot2]) = x;
        sort(v1 + 1, v1 + tot1 + 1);
        sort(v2 + 1, v2 + tot2 + 1);
        solve2();
        if (tot1 && m > v1[1]) solve1();
        cout << ans.first << ' ' << m - ans.second << endl;
    }
    return 0;
}
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n, g, r, q, d[N];
long long ans[N], mint[N * 4], tag[N * 4], eq[N * 4];
pair<int, int> a[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void build(int pos, int l, int r)
{
    mint[pos] = a[l].first;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
}

void lazy(int pos)
{
    if (eq[pos])
    {
        tag[lson] = tag[rson] = 0,
        eq[lson] = eq[rson] = eq[pos];
        mint[lson] = mint[rson] = eq[pos];
    }
    if (tag[pos])
    {
        tag[lson] += tag[pos], tag[rson] += tag[pos];
        mint[lson] += tag[pos], mint[rson] += tag[pos];
    }
    eq[pos] = tag[pos] = 0;
}

int find(int pos, int l, int r, long long t)
{
    if (mint[pos] >= t) return 0;
    if (l == r) return l;
    lazy(pos);
    int mid = (l + r) >> 1;
    if (mint[rson] >= t) return find(lson, l, mid, t);
    else return find(rson, mid + 1, r, t);
}

void modify(int pos, int l, int r, int x, int y, long long t)
{
    if (x <= l && r <= y)
    { tag[pos] = 0; eq[pos] = t; mint[pos] = t; return; }
    lazy(pos);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lson, l, mid, x, y, t);
    if (y > mid) modify(rson, mid + 1, r, x, y, t);
    mint[pos] = mint[lson];
}

void getans(int pos, int l, int r)
{
    if (l == r) { ans[a[l].second] += mint[pos]; return; }
    lazy(pos);
    int mid = (l + r) >> 1;
    getans(lson, l, mid); getans(rson, mid + 1, r);
}

int main()
{
    freopen("brt.in", "r", stdin);
    freopen("brt.out", "w", stdout);
    cin >> n >> g >> r;
    for (int i = 1; i <= n + 1; ++i)
        d[i] = read();
    cin >> q;
    for (int x, i = 1; i <= q; ++i)
    {
        x = read();
        ans[i] = x - x % (g + r), a[i] = make_pair(x % (g + r), i);
    }
    sort(a + 1, a + q + 1);
    build(1, 1, q);
    long long t = a[1].first;
    for (int i = 1; i <= n; ++i)
    {
        t += d[i];
        tag[1] += d[i], mint[1] += d[i];
        if (t % (g + r) >= g)
        {
            t = (t / (g + r) + 1) * (g + r);
            int x = find(1, 1, q, t);
            if (x) modify(1, 1, q, 1, x, t);
            x = find(1, 1, q, t + g);
            if (x < q) modify(1, 1, q, x + 1, q, t + g + r);
        }
        else
        {
            long long t2 = t / (g + r) * (g + r);
            int x = find(1, 1, q, t2 + g);
            int y = find(1, 1, q, t2 + g + r);
            if (x < y) modify(1, 1, q, x + 1, y, t2 + g + r);
        }
    }
    getans(1, 1, q);
    for (int i = 1; i <= q; ++i)
        printf("%lld\n", ans[i] + d[n + 1]);
    return 0;
}