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

void solve() {
    int n, m;
    cin >> n >> m;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vl b(m);
    rep(i, 0, m - 1) {
        cin >> b[i];
        b[i]--;
    }
    ll ans2 = 0;
    rep(i, 0, n - 1) ans2 += a[i];
    vl tem1;
    vl tem2;
    rep(i, 0, n - 1) {
        if (i % 2 == 0)
            tem1.push_back(a[i]);
        else
            tem2.push_back(a[i]);
    }
    sort(all2(tem1));
    sort(all2(tem2));
    int l = 0, r = 0;
    ll ans = 0;
    rep(i, 0, m - 1) {
        if (b[i] % 2 == 0) {
            if (l < sz(tem1) && tem1[l] >= 0) {
                ans += tem1[l];
                l++;
            } else if (l == 0 && sz(tem1) > 0) {
                ans += tem1[l];
                l++;
            }
        } else {
            if (r < sz(tem2) && tem2[r] >= 0) {
                ans += tem2[r];
                r++;
            } else if (r == 0 && sz(tem2) > 0) {
                ans += tem2[r];
                r++;
            }
        }
    }
    cout << ans2 - ans << endl;
    return;
}

 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

struct Mid {
    vi cnt;
    int res = 0;
    int cnt2 = 0;
    int l = 0;
    Mid(int x) : cnt(x, 0) {}

    void insert(int x) {
        l++;
        cnt[x]++;
        if (l == 1) {
            res = x;
            cnt2 = 1;
            return;
        }
        if (x <= res) cnt2++;
        int tem = (l + 1) / 2;
        while (res > 0 && cnt2 - cnt[res] >= tem) {
            cnt2 -= cnt[res];
            res--;
        }
        while (res < sz(cnt) - 1 && cnt2 < tem) {
            res++;
            cnt2 += cnt[res];
        }
    }
    int get() { return res; }
};
void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    int ans = 1;
    auto sorted = a;
    ranges::sort(sorted);
    sorted.erase(unique(all(sorted)), sorted.end());
    rep(i, 0, n - 1) {
        auto x = ranges::lower_bound(sorted, a[i]);
        a[i] = x - sorted.begin();
    }
    int m = sz(sorted);
    vvi dp(n + 1, vi(m, -1));
    rep(i, 0, m - 1) dp[0][i] = 0;
    rep(i, 0, n - 1) {
        Mid tem(m);
        rep(j, i, n - 1) {
            tem.insert(a[j]);
            if ((j - i + 1) % 2 == 0) continue;
            int mid = tem.get();
            if (dp[i][mid] != -1) dp[j + 1][mid] = max(dp[j + 1][mid], dp[i][mid] + 1);
        }
    }
    rep(i, 0, m - 1) { ans = max(ans, dp[n][i]); }
    cout << ans << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vector<pll> pre(n);
    vi res(n);
    rep(i, 1, n - 1) {
        pre[i].first = pre[i - 1].first + a[i - 1];
        pre[i].second = i;
    }
    sort(all(pre), [&](const pll& x, const pll& y) { return x.first < y.first; });
    rep(i, 0, n - 1) { res[pre[i].second] = n - i; }
    rep(i, 0, n - 1) cout << res[i] << ' ';
    cout << endl;
    return;
}

 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

void init(ll a) {
    cout << a << '\n';
    cout.flush();
    return;
}
ll insert(ll l) {
    cout << "I " << l << '\n';
    cout.flush();
    ll op;
    cin >> op;
    return op;
}
ll query(ll l) {
    cout << "Q " << l << '\n';
    cout.flush();
    ll op;
    cin >> op;
    return op;
}
void report(ll a, ll b) {
    cout << "A " << a << ' ' << b << '\n';
    cout.flush();
}
void solve() {
    int n;
    cin >> n;
    ll k = 0, c = 0;
    init((1LL << n) - 1);
    int tem = insert(0);
    if (tem == 1) {
        c = (1LL << n) - 1;
        int tem2 = insert((1LL << n) - 1);
        if (tem2 == 1)
            k = 2;
        else
            k = 3;
        report(k, c);
        return;
    } else {
        int tem2 = query(1);
        if (tem2 == 1) {
            k = 1;
            if (n == 1)
                c = 1;
            else {
                int tem3 = tem;
                rep(i, 0, n - 1) {
                    int tem4 = insert(1LL << i);
                    if (tem4 == tem3 + 1) c += (1LL << i);
                    tem3 = tem4;
                }
            }
            report(k, c);
            return;
        } else {
            ll l = 1, r = (1LL << n) - 2;
            while (l < r) {
                ll mid = (l + r + 1) / 2;
                ll tem3 = query(mid);
                if (tem3 == 2)
                    l = mid;
                else
                    r = mid - 1;
            }
            ll tem3 = insert(l);
            if (tem3 == 2)
                k = 2;
            else
                k = 3;
            report(k, l);
            return;
        }
    }
    return;
}