A1. Non-alternating Deck (easy version)

#include <bits/stdc++.h>
using namespace std;
int a, b, n;
void solve(){
    scanf("%d", &n), a = b = 0;
    for(int i = 1, now = 0; ; i ++){
        if(now+i > n){
            if(i % 4 == 1 || i % 4 == 0) a += n-now; else b += n-now;
            break;
        }
        if(i % 4 == 1 || i % 4 == 0) a += i; else b += i;
        now += i;
    }
    printf("%d %d\n", a, b);
}
int main(){int T; scanf("%d", &T); while(T--)solve();}

A2. Alternating Deck (hard version)

#include <bits/stdc++.h>
using namespace std;
int T, n, Aco1, Aco2, Bco1, Bco2;
void solve(){
    scanf("%d", &n); Aco1 = Aco2 = Bco1 = Bco2 = 0;
    int cp = n;
    for(int i = 1, now = 0; ; i++){
        if(now+i <= n){
            int x = n-now;
            if(i % 4 == 1 || i %4  == 0){
                if(i%4 == 1) Aco1 += i/2, Aco2 += i/2+1;
                else Aco1 += i/2, Aco2 += i/2;
            }
            else{
                if(i % 4 == 3) Bco1 += i/2+1, Bco2 += i/2;
                else Bco1 += i/2, Bco2 += i/2;
            }
            now += i;
            if(now == n) break;
        }
        else{
            if(i % 4 == 1 || i %4  == 0){
                for(int j = Aco1 + Aco2 + Bco1 + Bco2 + 1; j <= n; j ++) {
                    if(j % 2 == 1) Aco2++;
                    else Aco1++;
                }
            }
            else{
                for(int j = Aco1 + Aco2 + Bco1 + Bco2 + 1; j <= n; j ++) {
                    if(j % 2 == 1) Bco2++;
                    else Bco1++;
                }
            }
            break;
        }
    }
    printf("%d %d %d %d\n", Aco2, Aco1, Bco2, Bco1);
}
int main(){
    int T; scanf("%d", &T); while(T--)solve();
    return 0;
}

B. Cake Assembly Line

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7;
int n, a[N], b[N], h, w, L, R, T, i, j, k;
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d %d %d", &n, &w, &h), L = -INT_MAX, R = INT_MAX;
        for(i = 1; i <= n; i ++) scanf("%d", &a[i]);
        for(i = 1; i <= n; i ++) scanf("%d", &b[i]);
        for(i = 1; i <= n; i ++)L = max(L, (b[i]+h)-(a[i]+w)),R = min(R, (b[i]-h)-(a[i]-w));
        puts(L <= R ? "YES" : "NO");
    }
    return 0;
}

C. Monsters (easy version)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+11;
int T, n, i, a[N]; long long ans;
int main(){
    scanf("%d", &T);
    while(T--){
        ans = 0, scanf("%d", &n);
        for(i = 0; i < n; i ++) scanf("%d", &a[i]);
        sort(a, a+n); ans = a[0] - 1, a[0] = 1;
        for(i = 1; i < n; i ++){
            if(a[i] > a[i-1]+1) ans += a[i] - a[i-1] - 1;
            a[i] = (a[i] == a[i-1] ? a[i] : a[i-1]+1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

D. Letter Exchange

#include <bits/stdc++.h>
using namespace std;
#define nd12 ((int)((int)need[1][2].size()))
#define nd21 ((int)((int)need[2][1].size()))
#define nd13 ((int)((int)need[1][3].size()))
#define nd31 ((int)((int)need[3][1].size()))
#define nd23 ((int)((int)need[2][3].size()))
#define nd32 ((int)((int)need[3][2].size()))
long long ans;
int T, n, i, j, k, W, I, N;
vector<int> need[4][4];
int have[4][4];
void solve(){
    scanf("%d", &n); ans = 0;
    for(i = 1; i <= 3; i ++) for(j = 1; j <= 3; j ++) need[i][j].clear(), have[i][j] = 0;
    char r[4];
    for(k = 1; k <= n; k ++){
        scanf("%s", r+1); W = I = N = 0;
        for(i = 1; i <= 3; i ++){
            if(r[i] == 'w') W++;
            if(r[i] == 'i') I++;
            if(r[i] == 'n') N++;
        }
        if(W == I && I == N) continue;
        if(W == 0){
            if(I == 0){
                // w = 0 i = 0 n = 3
                need[3][1].push_back(k);
                need[3][2].push_back(k);
            }
            if(I == 1){
                // w = 0 i = 1 n = 2
                need[3][1].push_back(k);
            }
            if(I == 2){
                // w = 0 i = 2 n = 1
                need[2][1].push_back(k);
            }
            if(I == 3){
                // w = 0 i = 3 n = 0
                need[2][1].push_back(k);
                need[2][3].push_back(k);
            }
        }
        if(W == 1){
            if(I == 0){
                // w = 1 i = 0 n = 2
                need[3][2].push_back(k);
            }
            if(I == 2){
                // w = 1 i = 2 n = 0
                need[2][3].push_back(k);
            }
        }
        if(W == 2){
            if(I == 0){
                // w = 2 i = 0 n = 1
                need[1][2].push_back(k);
            }
            if(I == 1){
                // w = 2 i = 1 n = 0
                need[1][3].push_back(k);
            }
        }
        if(W == 3){
            // w = 3 i = 0 n = 0
            need[1][2].push_back(k);
            need[1][3].push_back(k);
        }
    }
    ans = min(nd12, nd21) + min(nd13, nd31) + min(nd23, nd32);
    have[1][2] = nd12 - min(nd12, nd21);
    have[2][1] = nd21 - min(nd12, nd21);
    have[1][3] = nd13 - min(nd13, nd31);
    have[3][1] = nd31 - min(nd13, nd31);
    have[2][3] = nd23 - min(nd23, nd32);
    have[3][2] = nd32 - min(nd23, nd32);
    ans += (min(have[1][2], min(have[2][3], have[3][1])) + min(have[2][1], min(have[1][3], have[3][2])))*2;
    printf("%lld\n", ans);
    while(nd12 > 0 && nd21 > 0){
        printf("%d w %d i\n", need[1][2][nd12-1], need[2][1][nd21-1]);
        need[1][2].pop_back(), need[2][1].pop_back();
    }
    while(nd13 > 0 && nd31 > 0){
        printf("%d w %d n\n", need[1][3][nd13-1], need[3][1][nd31-1]);
        need[1][3].pop_back(), need[3][1].pop_back();
    }
    while(nd23 > 0 && nd32 > 0){
        printf("%d i %d n\n", need[2][3][nd23-1], need[3][2][nd32-1]);
        need[2][3].pop_back(), need[3][2].pop_back();
    }
    while(nd12 > 0 && nd23 > 0 && nd31 > 0){
        printf("%d w %d i\n", need[1][2][nd12-1], need[2][3][nd23-1]);
        printf("%d w %d n\n", need[2][3][nd23-1], need[3][1][nd31-1]);
        need[1][2].pop_back(), need[2][3].pop_back(), need[3][1].pop_back();
    }
    while(nd21 > 0 && nd32 > 0 && nd13 > 0){
        printf("%d i %d w\n", need[2][1][nd21-1], need[1][3][nd13-1]);
        printf("%d i %d n\n", need[1][3][nd13-1], need[3][2][nd32-1]);
        need[2][1].pop_back(), need[3][2].pop_back(), need[1][3].pop_back();
    }
}
int main(){
    scanf("%d", &T);
    while(T--)solve();
    return 0;
}

E. Monsters (hard version)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+11;
int n;
struct sgt{
    int mn[N<<2], lazy[N<<2];
    #define lc ((k)<<(1))
    #define rc ((k)<<(1)|(1))
    #define mid ((l)+(r)>>(1))
    void up(int k){mn[k] = min(mn[lc], mn[rc]);}
    void down(int k){if(lazy[k]){lazy[lc] += lazy[k], lazy[rc] += lazy[k], mn[lc] += lazy[k], mn[rc] += lazy[k], lazy[k] = 0;}}
    void modify(int x, int y, int z, int k = 1, int l = 1, int r = n){
        if(l >= x && r <= y) {mn[k] += z, lazy[k] += z; return;}
        if(l > y || r < x) return; down(k);
        modify(x, y, z, lc, l, mid), modify(x, y, z, rc, mid+1, r), up(k);
    }
    void build(int k = 1, int l = 1, int r = n){
        lazy[k] = 0; if(l == r) {mn[k] = l;return;}
        build(lc, l, mid), build(rc, mid+1, r), up(k);
    }
    int ask(int k = 1, int l = 1, int r = n){
        if(mn[k] >= 0) return 0; if(l == r) return l;
        down(k); if(mn[lc] < 0) return ask(lc, l, mid); else return ask(rc, mid+1, r);
    }
}tree;
void solve(){
    scanf("%d", &n); long long ans = 0, L = 0; tree.build();
    for(int i = 1; i <= n; i ++){
        static int x, y; scanf("%d", &x);
        tree.modify(x, n, -1);
        y = tree.ask();
        if(y)ans += x - y, tree.modify(y, n, 1);
        else ans += x - (++L);
        printf("%lld ", ans);
    }
    puts("");
}
int main(){
    int T; scanf("%d", &T); while(T--) solve();return 0;
}