Codeforces训练记录

Codeforces Round #693 (Div. 3)

A - Cards for Friends

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

int T, w, h, n;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &w, &h, &n);
        int res = 1;
        while (0 == w % 2) {
            res *= 2;
            w /= 2;
        }
        while (0 == h % 2) {
            res *= 2;
            h /= 2;
        }
        if (res >= n) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

B - Fair Division

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

int T, n;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int a = 0, b = 0;
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            if (1 == x) a += 1;
            else b += 1;
        }
        if (0 == b % 2 && 0 == a % 2) printf("YES\n");
        else if (0 == b % 2 && 1 == a % 2) printf("NO\n");
        else if (1 == b % 2) {
            if (0 != a && 0 == a % 2) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

C - Long Jumps

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;

int T, n, a[N], dp[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            dp[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            if (i + a[i] > n) continue;
            dp[i + a[i]] = max(dp[i + a[i]], dp[i] + a[i]);
        }
        int res = 0;
        for (int i = 1; i <= n; i++) res = max(res, dp[i] + a[i]);
        printf("%d\n", res);
    }
    return 0;
}

D - Even-Odd Game

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;

int T, n;
ll a[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        sort(a + 1, a + n + 1);
        reverse(a + 1, a + n + 1);
        ll ra = 0, rb = 0;
        for (int i = 1; i <= n; i++) {
            if (1 == i % 2 && 0 == a[i] % 2) ra += a[i];
            if (0 == i % 2 && 1 == a[i] % 2) rb += a[i];
        }
        if (ra > rb) printf("Alice\n");
        else if (ra == rb) printf("Tie\n");
        else printf("Bob\n");
    }
    return 0;
}

E - Correct Placement

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 400010;
const int INF = 0x3f3f3f3f;

struct node {
    int w, h, id;
    node() { }
    node(int _w, int _h, int _id) : w(_w), h(_h), id(_id) { }
};

int T, n, res[N];
node a[N];
vector v;

bool cmp(node a, node b)
{
    if (a.h != b.h) return a.h < b.h;
    return a.w < b.w;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        v.clear();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i].h, &a[i].w);
            a[i].id = i;
            v.push_back(node(a[i].h, a[i].w, i));
            v.push_back(node(a[i].w, a[i].h, i));
        }
        sort(a + 1, a + n + 1, cmp);
        sort(v.begin(), v.end(), cmp);
        int p = -1, imin = INF, np = -1;
        for (int i = 1; i <= n; i++) {
            while (p + 1 < v.size() && v[p + 1].h < a[i].h) {
                p += 1;
                if (v[p].w < imin) {
                    imin = v[p].w;
                    np = v[p].id;
                }
            }
            if (imin < a[i].w) res[a[i].id] = np;
            else res[a[i].id] = -1;
        }
        for (int i = 1; i <= n; i++) {
            printf("%d", res[i]);
            printf(i == n ? "\n" : " ");
        }
    }
    return 0;
}

F - New Year's Puzzle

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 200010;

int T, n, m, r[N], c[N];
map<int, int> mp;
vector vo;

bool cmp(pii a, pii b)
{
    return a.second < b.second;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        vo.clear();
        mp.clear();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", &r[i], &c[i]);
            mp[c[i]] += 1;
        }
        for (int i = 1; i <= m; i++) {
            if (0 == mp[c[i]]) continue;
            if (2 == mp[c[i]]) {
                vo.push_back( { 3, c[i] } );
                mp[c[i]] = 0;
            }
            else vo.push_back( { r[i], c[i] } );
        }
        sort(vo.begin(), vo.end(), cmp);
        int f = 1, t = 0, lst = 0, tlst = 0;
        for (int i = 0; i < vo.size(); i++) {
            if (0 == t && 3 == vo[i].first) continue;
            if (0 == t) {
                t = 1;
                lst = vo[i].second;
                tlst = vo[i].first;
            }
            else {
                if (3 == vo[i].first) {
                    f = 0;
                    break;
                }
                int now = vo[i].second, tnow = vo[i].first;
                if ((0 == (now - lst) % 2 && tnow != tlst) || (1 == (now - lst) % 2 && tnow == tlst)) {
                    t = lst = tlst = 0;
                }
                else {
                    f = 0;
                    break;
                }
            }
        }
        if (0 != t) f = 0;
        printf(0 == f ? "NO\n" : "YES\n");
    }
    return 0;
}

Codeforces Round #667 (Div. 3)

A - Yet Another Two Integers Problem

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

int T, a, b;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &a, &b);
        printf("%d\n", (abs(a - b) + 9) / 10);
    }
    return 0;
}

B - Minimum Product

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

int T;
ll a, b, x, y, n;

ll solve(ll a, ll b, ll x, ll y, ll n)
{
    ll imin = min(n, a - x);
    n -= imin;
    a -= imin;
    imin = min(n, b - y);
    n -= imin;
    b -= imin;
    return a * b;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%lld%lld%lld", &a, &b, &x, &y, &n);
        printf("%lld\n", min(solve(a, b, x, y, n), solve(b, a, y, x, n)));
    }
    return 0;
}

C - Yet Another Array Restoration

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

int T, n, x, y;
vector<int> res;

void solve()
{
    res.clear();
    scanf("%d%d%d", &n, &x, &y);
    for (int i = 1; i <= y - x; i++) {
        if (0 != (y - x) % i) continue;
        if ((y - x) / i + 1 > n) continue;
        int cnt = 0;
        for (int j = x; j <= y && cnt < n; j += i, cnt++) res.push_back(j);
        for (int j = x - i; j > 0 && cnt < n; j -= i, cnt++) res.push_back(j);
        for (int j = y + i; cnt < n; j += i, cnt++) res.push_back(j);
        break;
    }
    for (int i = 0; i < res.size(); i++) {
        printf("%d", res[i]);
        printf(i == res.size() - 1 ? "\n" : " ");
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

D - Decrease the Sum of Digits

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 20;
const ll INF = 1000000000000000000;

int T, s, a[N], b[N];
ll n;

void solve()
{
    for (int i = 0; i < N; i++) a[i] = 0;
    scanf("%lld%d", &n, &s);
    ll tn = n, res = INF;
    int cnt = 0, sum = 0;
    while (tn) {
        a[++cnt] = tn % 10;
        sum += a[cnt];
        tn /= 10;
    }
    if (sum <= s) {
        printf("0\n");
        return;
    }
    for (int i = 2; i <= cnt + 1; i++) {
        for (int j = 0; j < N; j++) b[j] = a[j];
        if (9 == b[i]) continue;
        b[i] += 1;
        for (int j = i - 1; j >= 1; j--) b[j] = 0;
        int tsum = 0;
        for (int j = 0; j < N; j++) tsum += b[j];
        if (tsum > s) continue;
        ll now = 0;
        for (int j = N - 1; j >= 1; j--) now = now * 10 + b[j];
        res = min(res, now - n);
    }
    printf("%lld\n", res);
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

E - Two Platforms

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 200010;

int T, n, k, x[N], y[N], dp[N];

void solve()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &y[i]);
    for (int i = 1; i <= n; i++) dp[i] = 0;
    sort(x + 1, x + n + 1);
    int l = 1, imax = 0;
    for (int i = 1; i <= n; i++) {
        while (x[i] - x[l] > k) l += 1;
        dp[i] = max(dp[i - 1], i - l + 1);
        imax = max(imax, dp[l - 1] + i - l + 1);
    }
    printf("%d\n", imax);
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

Codeforces Round #694 (Div. 2)

A - Strange Partition

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 100010;

int T, n;
ll x, a[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%lld", &n, &x);
        ll imax = 0, imin = 0, sum = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            imax = imax + (a[i] + x - 1) / x;
            sum += a[i];
        }
        printf("%lld %lld\n", (sum + x - 1) / x, imax);
    }
    return 0;
}

B - Strange List

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 100010;

struct node {
    ll q, cnt;
    node() { }
    node(ll _q, ll _cnt) : q(_q), cnt(_cnt) { }
};

int T, n;
ll x, a[N];
queue que;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%lld", &n, &x);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            que.push(node(a[i], 1));
        }
        ll res = 0;
        while (!que.empty()) {
            node nd = que.front();
            if (nd.q % x) break;
            que.pop();
            res += nd.q * nd.cnt;
            que.push(node(nd.q / x, x * nd.cnt));
        }
        while (!que.empty()) {
            node nd = que.front();
            que.pop();
            res += nd.q * nd.cnt;
        }
        printf("%lld\n", res);
    }
    return 0;
}

C - Strange Birthday Party

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 300010;

struct node {
    int k, id;
};

int T, n, m;
ll c[N];
node nd[N];

bool cmp(node a, node b)
{
    if (c[a.k] != c[b.k]) return c[a.k] > c[b.k];
    return a.id > b.id;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &nd[i].k);
            nd[i].id = i;
        }
        for (int i = 1; i <= m; i++) scanf("%lld", &c[i]);
        sort(nd + 1, nd + n + 1, cmp);
        ll res = 0;
        int p = 1;
        for (int i = 1; i <= n; i++) {
            if (p <= m) {
                if (nd[i].k < p) res += c[nd[i].k];
                else {
                    if (c[p] < c[nd[i].k]) {
                        res += c[p];
                        p += 1;
                    }
                    else res += c[nd[i].k];
                }
            }
            else res += c[nd[i].k];
        }
        printf("%lld\n", res);
    }
    return 0;
}

D - Strange Definition

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 1000010;

int T, n, q, tot;
int a[N], isp[N], p[N];
unordered_map<int, int> mp;
vector<int> v;

void init(int n)
{
    for (int i = 2; i <= n; i++) {
        if (!isp[i]) p[++tot] = i;
        for (int j = 1; j <= tot && p[j] <= n / i; j++) {
            isp[i * p[j]] = 1;
            if (0 == i % p[j]) break;
        }
    }
}

void divide(int n)
{
    int res = 1;
    for (int i = 1; i <= tot; i++) {
        int cnt = 0;
        while (0 == n % p[i]) {
            n /= p[i];
            cnt += 1;
        }
        if (1 == cnt % 2) res *= p[i];
        if (n < 1ll * p[i] * p[i]) break;
    }
    if (n > 1) res *= n;
    mp[res] += 1;
    v.push_back(res);
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    init(N - 5);
    scanf("%d", &T);
    while (T--) {
        v.clear();
        mp.clear();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            divide(a[i]);
        }
        int r1 = 0, r2 = mp[1];
        for (int i = 0; i < v.size(); i++) r1 = max(r1, mp[v[i]]);
        for (int i = 0; i < v.size(); i++) {
            if (1 == v[i]) continue;
            if (0 == mp[v[i]] % 2) {
                r2 += mp[v[i]];
                mp[v[i]] = 0;
            }
        }
        r2 = max(r1, r2);
        scanf("%d", &q);
        while (q--) {
            ll w;
            scanf("%lld", &w);
            printf("%d\n", w ? r2 : r1);
        }
    }
    return 0;
}

F - Strange Housing

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 300010;

struct Edge {
    int to, nex;
};

int T, n, m, cnt, head[N], vis[N];
Edge edge[2 * N];
vector<int> v;

void init()
{
    cnt = 0;
    v.clear();
    for (int i = 1; i <= n; i++) head[i] = vis[i] = 0;
}

void add_edge(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

void dfs(int u)
{
    int f = 0;
    for (int i = head[u]; 0 != i; i = edge[i].nex) {
        int v = edge[i].to;
        if (2 == vis[v]) f = 1;
    }
    if (1 == f) vis[u] = 1;
    else vis[u] = 2;
    for (int i = head[u]; 0 != i; i = edge[i].nex) {
        int v = edge[i].to;
        if (vis[v]) continue;
        dfs(v);
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        init();
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            add_edge(u, v);
            add_edge(v, u);
        }
        dfs(1);
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (2 == vis[i]) v.push_back(i);
            if (vis[i]) cnt++;
        }
        if (cnt < n) {
            printf("NO\n");
            continue;
        }
        printf("YES\n%d\n", v.size());
        for (int i = 0; i < v.size(); i++) {
            printf("%d", v[i]);
            printf(i == v.size() - 1 ? "\n" : " ");
        }
    }
    return 0;
}

Codeforces Round #690 (Div. 3)

A - Favorite Sequence

#include 
#include 
#include 
#include 

using namespace std;

const int N = 310;

int T, n, a[N], res[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        int l = 1, r = n;
        for (int i = 1; i <= n; i++) {
            if (i & 1) res[i] = a[l++];
            else res[i] = a[r--];
        }
        for (int i = 1; i <= n; i++) {
            printf("%d", res[i]);
            printf(i == n ? "\n" : " ");
        }
    }
    return 0;
}

B - Last Year's Substring

#include 
#include 
#include 
#include 

using namespace std;

const int N = 210;

int T, n;
char s[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%s", &n, s + 1);
        int len = strlen(s + 1), ok = 0;
        if ('2' == s[1] && '0' == s[2] && '2' == s[3] && '0' == s[4]) ok = 1;
        if ('2' == s[1] && '0' == s[2] && '2' == s[3] && '0' == s[n]) ok = 1;
        if ('2' == s[1] && '0' == s[2] && '2' == s[n - 1] && '0' == s[n]) ok = 1;
        if ('2' == s[1] && '0' == s[n - 2] && '2' == s[n - 1] && '0' == s[n]) ok = 1;
        if ('2' == s[n - 3] && '0' == s[n - 2] && '2' == s[n - 1] && '0' == s[n]) ok = 1;
        printf(1 == ok ? "YES\n" : "NO\n");
    }
    return 0;
}

C - Unique Number

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

int T, n;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        if (n > 45) {
            printf("-1\n");
            continue;
        }
        int now = 9, res = 0, b = 1;
        while (n) {
            int imin = min(now, n);
            res = res + b * imin;
            b *= 10;
            now -= 1;
            n -= imin;
        }
        printf("%d\n", res);
    }
    return 0;
}

D - Add to Neighbour and Remove

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 3010;

int T, n, a[N], sum[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            sum[i] = sum[i - 1] + a[i];
        }
        int res = 1;
        for (int i = 1; i <= n; i++) {
            int cnt = 1, s = sum[i], p = i + 1, ts = 0, f = 1;
            while (p <= n) {
                ts += a[p];
                p += 1;
                if (ts == s) {
                    ts = 0;
                    cnt += 1;
                }
                if (ts > s) {
                    f = 0;
                    break;
                }
            }
            if (0 != ts) f = 0;
            if (f) res = max(res, cnt);
        }
        printf("%d\n", n - res);
    }
    return 0;
}

E1 - Close Tuples (easy version)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 200010;
const ll mod = 1000000007;

int T, n, a[N];

ll C(int n)
{
    return 1ll * n * (n - 1) / 2;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        if (n < 3) {
            printf("0\n");
            continue;
        }
        int l = 1;
        ll res = 0;
        for (int i = 3; i <= n; i++) {
            while (a[i] - a[l] > 2) l += 1;
            if (i - l + 1 < 3) continue;
            res += C(i - l);
        }
        printf("%lld\n", res);
    }
    return 0;
}

E2 - Close Tuples (hard version)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 200010;
const ll mod = 1000000007;

int T, n, m, k, a[N];
ll fac[N], inv[N];

void init()
{
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
    inv[1] = 1;
    for (int i = 2; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    inv[0] = 1;
    for (int i = 1; i < N; i++) inv[i] = inv[i] * inv[i - 1] % mod;
}

ll C(int n, int m)
{
    ll res = fac[n] * inv[m] % mod * inv[n - m] % mod;
    return res;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    init();
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        if (m > n) {
            printf("0\n");
            continue;
        }
        int l = 1;
        ll res = 0;
        for (int i = m; i <= n; i++) {
            while (a[i] - a[l] > k) l += 1;
            if (i - l + 1 < m) continue;
            res = (res + C(i - l, m - 1)) % mod;
        }
        printf("%lld\n", res);
    }
    return 0;
}

F - The Treasure of The Segments

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 1000010;

int T, n, l[N], r[N], cl[N], cr[N];
vector<int> alls;

int get_id(int x)
{
    return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        alls.clear();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &l[i], &r[i]);
            alls.push_back(l[i]);
            alls.push_back(r[i]);
            alls.push_back(l[i] - 1);
            alls.push_back(r[i] + 1);
        }
        sort(alls.begin(), alls.end());
        alls.erase(unique(alls.begin(), alls.end()), alls.end());
        for (int i = 0; i <= alls.size() + 1; i++) cl[i] = cr[i] = 0;
        for (int i = 1; i <= n; i++) {
            cl[get_id(r[i])] += 1;
            cr[get_id(l[i])] += 1;
        }
        for (int i = 1; i <= alls.size(); i++) cl[i] += cl[i - 1];
        for (int i = alls.size(); i >= 1; i--) cr[i] += cr[i + 1];
        int res = n;
        for (int i = 1; i <= n; i++) {
            int idl = get_id(l[i] - 1), idr = get_id(r[i] + 1);
            res = min(res, cl[idl] + cr[idr]);
        }
        printf("%d\n", res);
    }
    return 0;
}

Good Bye 2020

A - Bovine Dilemma

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 60;

int T, n, a[N];
set<int> st;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        st.clear();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) {
            for (int k = i + 1; k <= n; k++) {
                st.insert(a[k] - a[i]);
            }
        }
        printf("%d\n", st.size());
    }
    return 0;
}

B - Last minute enhancements

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 1000010;

int T, n, c[N], vis[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= 2 * n + 1; i++) c[i] = vis[i] = 0;
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            c[x] += 1;
        }
        for (int i = 1; i <= 2 * n; i++) {
            if (0 == c[i]) continue;
            if (0 == vis[i]) {
                if (1 == c[i]) vis[i] = 1;
                else vis[i] = vis[i + 1] = 1;
            }
            else vis[i + 1] = 1;
        }
        int res = 0;
        for (int i = 1; i <= 2 * n + 1; i++) res += vis[i];
        printf("%d\n", res);
    }
    return 0;
}

C - Canine poetry

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 1000010;

int T, f[N];
char s[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s + 1);
        int len = strlen(s + 1), res = 0;
        for (int i = 1; i <= len; i++) f[i] = 0;
        for (int i = 1; i <= len; i++) {
            if (1 == f[i]) continue;
            if (0 == f[i] && i + 1 <= len && s[i] == s[i + 1]) {
                res += 1;
                f[i + 1] = 1;
            }
            if (0 == f[i] && i + 2 <= len && s[i] == s[i + 2]) {
                res += 1;
                f[i + 2] = 1;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

D - 13th Labour of Heracles

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 100010;

struct node {
    int id, cnt;
    ll w;
    node(int _id, int _cnt, ll _w) : id(_id), cnt(_cnt), w(_w) { }
};

int T, n, deg[N];
ll w[N];
vector v;
vector res;

bool cmp(node a, node b)
{
    return a.w > b.w;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        res.clear();
        v.clear();
        scanf("%d", &n);
        ll sum = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &w[i]);
            deg[i] = 0;
            sum += w[i];
        }
        for (int i = 1; i <= n - 1; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            deg[u] += 1;
            deg[v] += 1;
        }
        for (int i = 1; i <= n; i++) {
            if (1 == deg[i]) continue;
            v.push_back(node(i, deg[i], w[i]));
        }
        sort(v.begin(), v.end(), cmp);
        res.push_back(sum);
        int p = 0;
        for (int i = 2; i <= n - 1; i++) {
            while (1 == v[p].cnt) p += 1;
            sum += v[p].w;
            res.push_back(sum);
            v[p].cnt -= 1;
        }
        for (int i = 0; i < res.size(); i++) {
            printf("%lld", res[i]);
            printf(i == res.size() - 1 ? "\n" : " ");
        }
    }
    return 0;
}

E - Apollo versus Pan

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 500010;
const ll mod = 1000000007;

int T, n;
ll w[N], s[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i <= 60; i++) s[i] = 0;
        for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
        for (int i = 0; i <= 60; i++) {
            ll base = (1ll << i);
            for (int k = 1; k <= n; k++) {
                if (w[k] & base) s[i] = (s[i] + base % mod) % mod;
            }
        }
        ll res = 0;
        for (int i = 1; i <= n; i++) {
            ll a = 0, b = 0;
            for (int k = 0; k <= 60; k++) {
                ll base = (1ll << k);
                if (w[i] & base) {
                    a = (a + s[k]) % mod;
                    b = (b + base % mod * n % mod) % mod;
                }
                else b = (b + s[k]) % mod;
            }
            res = (res + a * b % mod) % mod;
        }
        printf("%lld\n", res);
    }
    return 0;
}

F - Euclid's nightmare

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 500010;
const ll mod = 1000000007;

int n, m, fa[N];
vector<int> res;

void init()
{
    for (int i = 1; i <= m + 1; i++) fa[i] = i;
}

int find(int x)
{
    return (fa[x] == x) ? x : (fa[x] = find(fa[x]));
}

bool nuio(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        fa[fx] = fy;
        return true;
    }
    return false;
}

ll power(ll a, ll n)
{
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d%d", &n, &m);
    init();
    for (int i = 1; i <= n; i++) {
        int k, a, b;
        scanf("%d%d", &k, &a);
        if (1 == k) b = m + 1;
        else scanf("%d", &b);
        if (nuio(a, b)) res.push_back(i);
    }
    printf("%lld %d\n", power(2, res.size()), res.size());
    for (int i = 0; i < res.size(); i++) {
        printf("%d", res[i]);
        printf(i == res.size() - 1 ? "\n" : " ");
    }
    return 0;
}

Codeforces Round #634 (Div. 3)

A - Candies and Two Sisters

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

int T, n;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%d\n", 0 == n % 2 ? n / 2 - 1 : n / 2);
    }
    return 0;
}

B - Construct the String

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

int T, n, a, b;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &a, &b);
        for (int i = 0; i < n; i++) printf("%c", char('a' + i % b));
        printf("\n");
    }
    return 0;
}

C - Two Teams Composing

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 200010;

int T, n, c[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) c[i] = 0;
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            c[x] += 1;
        }
        int imax = 0, cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (0 == c[i]) continue;
            imax = max(imax, c[i]);
            cnt += 1;
        }
        if (imax < cnt) printf("%d\n", imax);
        else if (imax == cnt) printf("%d\n", cnt - 1);
        else printf("%d\n", cnt);
    }
    return 0;
}

D - Anti-Sudoku

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 110;

int T;
char c[N][N];

void change(int x, int y)
{
    int now = c[x][y] - '0';
    if (9 == now) now = 1;
    else now = now + 1;
    c[x][y] = char(now + '0');
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        for (int i = 1; i <= 9; i++) scanf("%s", c[i] + 1);
        change(1, 1);
        change(2, 4);
        change(3, 7);
        change(4, 2);
        change(5, 5);
        change(6, 8);
        change(7, 3);
        change(8, 6);
        change(9, 9);
        for (int i = 1; i <= 9; i++) printf("%s\n", c[i] + 1);
    }
    return 0;
}

E1 - Three Blocks Palindrome (easy version)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 200010;
const int M = 210;

int T, n, a[N], b[M][N], bn[M], c[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= 200; i++) bn[i] = 0;
        for (int i = n; i >= 1; i--) {
            bn[a[i]] += 1;
            b[a[i]][bn[a[i]]] = i;
        }
        int res = 0;
        for (int i = 1; i <= 200; i++) res = max(res, bn[i]);
        for (int i = 1; i <= 200; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[j] == i) c[j] = c[j - 1] + 1;
                else c[j] = c[j - 1];
            }
            for (int j = 1; j <= 200; j++) {
                for (int k = 1; 2 * k <= bn[j]; k++) {
                    int l = b[j][bn[j] - k + 1] + 1, r = b[j][k] - 1;
                    res = max(res, 2 * k + c[r] - c[l - 1]);
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

E2 - Three Blocks Palindrome (hard version)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 200010;
const int M = 210;

int T, n, a[N], b[M][N], bn[M], c[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= 200; i++) bn[i] = 0;
        for (int i = n; i >= 1; i--) {
            bn[a[i]] += 1;
            b[a[i]][bn[a[i]]] = i;
        }
        int res = 0;
        for (int i = 1; i <= 200; i++) res = max(res, bn[i]);
        for (int i = 1; i <= 200; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[j] == i) c[j] = c[j - 1] + 1;
                else c[j] = c[j - 1];
            }
            for (int j = 1; j <= 200; j++) {
                for (int k = 1; 2 * k <= bn[j]; k++) {
                    int l = b[j][bn[j] - k + 1] + 1, r = b[j][k] - 1;
                    res = max(res, 2 * k + c[r] - c[l - 1]);
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

Educational Codeforces Round 101 (Rated for Div. 2)

A - Regular Bracket Sequence

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 110;

int T;
char s[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s + 1);
        int len = strlen(s + 1), l = 0, r = 0;
        for (int i = 1; i <= len; i++) {
            if ('(' == s[i]) l = i;
            if (')' == s[i]) r = i;
        }
        if (1 == (len - 2) % 2) {
            printf("NO\n");
            continue;
        }
        if (l < r || (l < len && r > 1)) {
            printf("YES\n");
            continue;
        }
        printf("NO\n");
    }
    return 0;
}

B - Red and Blue

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 110;

int T, n, m, a[N], b[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int maxa = 0, maxb = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            a[i] += a[i - 1];
            maxa = max(maxa, a[i]);
        }
        scanf("%d", &m);
        for (int i = 1; i <= m; i++) {
            scanf("%d", &b[i]);
            b[i] += b[i - 1];
            maxb = max(maxb, b[i]);
        }
        printf("%d\n", maxa + maxb);
    }
    return 0;
}

C - Building a Fence

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;

const int N = 200010;

int T, n;
ll k, h[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%lld", &n, &k);
        for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
        ll l = h[1], r = h[1];
        int f = 1;
        for (int i = 2; i <= n; i++) {
            r = min(h[i] + k - 1, r + k - 1);
            l = max(h[i], l - k + 1);
            if (r >= l) continue;
            f = 0;
            break;
        }
        if (1 == f && h[n] == l) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

D - Ceil Divisions

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 200010;

int T, n;
vector v;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        v.clear();
        scanf("%d", &n);
        int t = n;
        while (true) {
            if (t <= 2) break;
            int x = int(sqrt(t));
            if (x * x < t) x += 1;
            for (int i = x + 1; i < t; i++) v.push_back( { i, t } );
            v.push_back( { t, x } );
            v.push_back( { t, x } );
            t = x;
        }
        printf("%d\n", v.size());
        for (int i = 0; i < v.size(); i++) printf("%d %d\n", v[i].first, v[i].second);
    }
    return 0;
}

E - A Bit Similar

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1000010;
const int M = 20;

int T, n, k, cnt, sum[N];
unordered_map<int, int> mp;
char s[N], res[N];

void Hash(int l, int r)
{
    int res = 0;
    for (int i = l; i <= r; i++) res = res * 2 + s[i] - '0';
    mp[res] = 1;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        mp.clear();
        cnt = 0;
        scanf("%d%d%s", &n, &k, s + 1);
        for (int i = 1; i <= n; i++) s[i] = char(2 * '0' - s[i] + 1);
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + s[i] - '0';
        for (int i = 1; i + k - 1 <= n; i++) {
            if (k > M && sum[i + k - 1 - M] - sum[i - 1] >= 1) continue;
            if (k <= M) Hash(i, i + k - 1);
            else Hash(i + k - M, i + k - 1);
        }
        for (int i = 0; i < (1 << min(M, k)); i++) {
            if (mp[i]) continue;
            for (int j = 0; j < max(k - M, 0); j++) res[++cnt] = '0';
            for (int j = min(k, M) - 1; j >= 0; j--) {
                if ((i >> j) & 1) res[++cnt] = '1';
                else res[++cnt] = '0';
            }
            break;
        }
        res[cnt + 1] = '\0';
        if (0 == cnt) printf("NO\n");
        else printf("YES\n%s\n", res + 1);
    }
    return 0;
}

Codeforces Round #686 (Div. 3)

A - Special Permutation

#include 
#include 
#include 
#include 

using namespace std;

int T, n;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        if (n & 1) {
            for (int i = 1; i <= n - 3; i += 2) printf("%d %d ", i + 1, i);
            printf("%d %d %d\n", n - 1, n, n - 2);
        }
        else {
            for (int i = 1; i <= n; i += 2) {
                printf("%d %d", i + 1, i);
                if (i + 1 == n) printf("\n");
                else printf(" ");
            }
        }
    }
    return 0;
}

B - Unique Bid Auction

#include 
#include 
#include 
#include 

using namespace std;

const int N = 200010;

int T, n, res, now, c[N], val[N];

int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) c[i] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &val[i]);
            c[val[i]]++;
        }
        res = -1;
        now = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++) {
            if (1 != c[val[i]]) continue;
            if (val[i] < now) {
                now = val[i];
                res = i;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

C - Sequence Transformation

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 200010;
const int INF = 0x3f3f3f3f;

int T, n;
vector<int> p[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            p[i].clear();
            p[i].push_back(0);
        }
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            p[x].push_back(i);
        }
        for (int i = 1; i <= n; i++) p[i].push_back(n + 1);
        int res = INF;
        for (int i = 1; i <= n; i++) {
            if (2 == p[i].size()) continue;
            int cnt = 0;
            for (int j = 1; j < p[i].size(); j++) {
                if (p[i][j] - p[i][j - 1] == 1) continue;
                cnt += 1;
            }
            res = min(res, cnt);
        }
        printf("%d\n", res);
    }
    return 0;
}

D - Number into Sequence

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 200010;

int T, m;
ll n, imax, p[N], c[N];
vector res;

void divide(ll n)
{
    m = imax = 0;
    for (ll i = 2; i <= sqrt(n); i++) {
        if (0 != n % i) continue;
        p[++m] = i;
        c[m] = 0;
        while (0 == n % i) {
            n /= i;
            c[m] += 1;
        }
        imax = max(imax, c[m]);
    }
    if (n > 1) {
        p[++m] = n;
        c[m] = 1;
        imax = max(imax, c[m]);
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        res.clear();
        scanf("%lld", &n);
        divide(n);
        ll now = 1;
        for (int i = 1; i <= m; i++) {
            if (c[i] != imax) continue;
            for (int j = 0; j < c[i]; j++) {
                res.push_back(p[i]);
                now *= p[i];
            }
            break;
        }
        res[res.size() - 1] *= (n / now);
        printf("%d\n", res.size());
        for (int i = 0; i < res.size(); i++) {
            printf("%lld", res[i]);
            printf(i == res.size() - 1 ? "\n" : " ");
        }
    }
    return 0;
}

E - Number of Simple Paths

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;

struct Edge {
    int to, nex;
};

int T, n, cnt, tot;
int head[N], deg[N], vis[N], num[N];
Edge edge[2 * N];
queue<int> q;

void init()
{
    cnt = tot = 0;
    for (int i = 1; i <= n; i++) head[i] = vis[i] = deg[i] = 0;
    while (!q.empty()) q.pop();
}

void add_edge(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int dfs(int u, int fa)
{
    int res = 0;
    for (int i = head[u]; 0 != i; i = edge[i].nex) {
        int v = edge[i].to;
        if (0 == vis[v] || v == fa) continue;
        res = res + dfs(v, u) + 1;
    }
    return res;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        init();
        for (int i = 1; i <= n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            add_edge(u, v);
            add_edge(v, u);
            deg[u] += 1;
            deg[v] += 1;
        }
        for (int i = 1; i <= n; i++) {
            if (1 != deg[i]) continue;
            q.push(i);
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = 1;
            for (int i = head[u]; 0 != i; i = edge[i].nex) {
                int v = edge[i].to;
                deg[v] -= 1;
                if (1 == deg[v]) q.push(v);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;
            num[++tot] = dfs(i, -1);
        }
        ll res = 1ll * tot * (tot - 1);
        for (int i = 1; i <= tot; i++) {
            res = res + 2 * (n - tot) - num[i];
            res = res + 1ll * num[i] * (num[i] - 1) / 2;
            res = res + 1ll * num[i] * (n - tot - num[i]);
        }
        printf("%lld\n", res);
    }
    return 0;
}

Codeforces Round #627 (Div. 3)

A - Yet Another Tetris Problem

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 110;

int T, n, a[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int imax = 0, f = 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            imax = max(imax, a[i]);
        }
        for (int i = 1; i <= n; i++) {
            if (0 == (imax - a[i]) % 2) continue;
            f = 0;
            break;
        }
        if (f) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

B - Yet Another Palindrome Problem

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 5010;
const int INF = 0x3f3f3f3f;

int T, n, a[N], imin[N], imax[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            imin[i] = INF;
            imax[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            imin[a[i]] = min(imin[a[i]], i);
            imax[a[i]] = max(imax[a[i]], i);
        }
        int f = 0;
        for (int i = 1; i <= n; i++) {
            if (imax[a[i]] - imin[a[i]] >= 2) {
                f = 1;
                break;
            }
        }
        printf(f ? "YES\n" : "NO\n");
    }
    return 0;
}

C - Frog Jumps

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;
const int INF = 0x3f3f3f3f;

int T, lr[N];
char s[N];

bool check(int mid, int n)
{
    int pos = 0;
    while (pos + mid < n + 1) {
        if (lr[pos + mid] <= pos) return false;
        pos = lr[pos + mid];
    }
    return true;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s + 1);
        int now = -INF, len = strlen(s + 1);
        for (int i = 1; i <= len; i++) {
            if ('R' == s[i]) now = i;
            lr[i] = now;
        }
        int l = 1, r = len + 1;
        while (r > l) {
            int mid = (l + r) / 2;
            if (check(mid, len)) r = mid;
            else l = mid + 1;
        }
        printf("%d\n", l);
    }
    return 0;
}

D - Pair of Topics

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 400010;
const int INF = 0x3f3f3f3f;

int n, a[N], b[N], c[N];
vector<int> alls;

int get_id(int x)
{
    return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i++) {
        alls.push_back(b[i] - a[i]);
        alls.push_back(a[i] - b[i] - 1);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());;
    for (int i = 1; i <= n; i++) c[get_id(b[i] - a[i])] += 1;
    for (int i = 1; i <= alls.size(); i++) c[i] += c[i - 1];
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        res += c[get_id(a[i] - b[i] - 1)];
        if (a[i] > b[i]) res -= 1;
    }
    printf("%lld\n", res / 2);
    return 0;
}

E - Sleeping Schedule

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 2010;
const int INF = 0x3f3f3f3f;

int n, h, l, r, sum[N], a[N], dp[N][N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d%d%d%d", &n, &h, &l, &r);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int k = 0; k <= i; k++) {
            int now = (sum[i] - k) % h;
            if (now >= l && now <= r) now = 1;
            else now = 0;
            if (0 != k) dp[i][k] = max(dp[i][k], dp[i - 1][k - 1] + now);
            if (i >= k + 1) dp[i][k] = max(dp[i][k], dp[i - 1][k] + now);
        }
    }
    int res = 0;
    for (int i = 0; i <= n; i++) res = max(res, dp[n][i]);
    printf("%d\n", res);
    return 0;
}

Codeforces Round #676 (Div. 2)

A - XORwice

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

int T, a, b;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &a, &b);
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            int ta = (1 << i) & a, tb = (1 << i) & b;
            if (ta == tb) continue;
            res = res + (1 << i);
        }
        printf("%d\n", res);
    }
    return 0;
}

B - Putting Bricks in the Wall

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 210;

int T, n;
char s[N][N];
vector v;

bool check(char a, char b)
{
    v.clear();
    if (s[1][2] != a) v.push_back( { 1, 2 } );
    if (s[2][1] != a) v.push_back( { 2, 1 } );
    if (s[n][n - 1] != b) v.push_back( { n, n - 1 } );
    if (s[n - 1][n] != b) v.push_back( { n - 1, n } );
    if (v.size() <= 2) {
        printf("%d\n", v.size());
        for (int i = 0; i < v.size(); i++) printf("%d %d\n", v[i].first, v[i].second);
        return true;
    }
    return false;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
        if (!check('0', '1')) check('1', '0');
    }
    return 0;
}

C - Palindromifier

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 100010;

char s[N];
int len;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    printf("3\n");
    printf("R %d\n", len - 1);
    printf("L %d\n", len);
    printf("L 2\n");
}

D - Hexagons

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 100010;

int T;
ll x, y, c1, c2, c3, c4, c5, c6;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &x, &y);
        scanf("%lld%lld%lld%lld%lld%lld", &c1, &c2, &c3, &c4, &c5, &c6);
        if (x >= 0 && y >= 0) {
            ll res = x * c6 + y * c2;
            res = min(res, c1 * min(x, y) + c6 * (x - min(x, y)) + c2 * (y - min(x, y)));
            if (x <= y) res = min(res, y * c1 + c3 * (y - x));
            else res = min(res, x * c1 + c5 * (x - y));
            printf("%lld\n", res);
            continue;
        }
        else if (x <= 0 && y <= 0) {
            x = -x;
            y = -y;
            ll res = x * c3 + y * c5;
            res = min(res, c4 * min(x, y) + c3 * (x - min(x, y)) + c5 * (y - min(x, y)));
            if (x >= y) res = min(res, c4 * x + c2 * (x - y));
            else res = min(res, c4 * y + c6 * (y - x));
            printf("%lld\n", res);
            continue;
        }
        else if (x >= 0 && y <= 0) {
            y = -y;
            ll res = min(c6 * (x + y) + c4 * y, c5 * (x + y) + c1 * x);
            res = min(res, c6 * x + c5 * y);
            printf("%lld\n", res);
            continue;
        }
        else {
            x = -x;
            ll res = min(c3 * (x + y) + c1 * y, c2 * (x + y) + c4 * x);
            res = min(res, c3 * x + c2 * y);
            printf("%lld\n", res);
            continue;
        }
    }
    return 0;
}

Codeforces Round #605 (Div. 3)

A - Three Friends

#include 
#include 
#include 
#include 
#include 
#include 
#include <set>

using namespace std;

typedef long long ll;

const int N = 100010;
const int INF = 0x3f3f3f3f;

int T, a, b, c;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &a, &b, &c);
        int imin = min(a, min(b, c)), imax = max(a, max(b, c));
        if (imin != imax) imax -= 1;
        if (imin != imax) imin += 1;
        printf("%d\n", 2 * (imax - imin));
    }
    return 0;
}

B - Snow Walking Robot

#include 
#include 
#include 
#include 
#include 
#include 
#include <set>

using namespace std;

typedef long long ll;

const int N = 100010;
const int INF = 0x3f3f3f3f;

int T;
char s[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s + 1);
        int l = 0, r = 0, u = 0, d = 0, len = strlen(s + 1);
        for (int i = 1; i <= len; i++) {
            if ('D' == s[i]) d += 1;
            if ('R' == s[i]) r += 1;
            if ('L' == s[i]) l += 1;
            if ('U' == s[i]) u += 1;
        }
        int a = min(l, r), b = min(u, d);
        if (0 == a && 0 == b) printf("0\n\n");
        else if (0 == a && 0 != b) printf("2\nUD\n");
        else if (0 != a && 0 == b) printf("2\nLR\n");
        else {
            printf("%d\n", 2 * (a + b));
            for (int i = 1; i <= a; i++) printf("L");
            for (int i = 1; i <= b; i++) printf("U");
            for (int i = 1; i <= a; i++) printf("R");
            for (int i = 1; i <= b; i++) printf("D");
            printf("\n");
        }
    }
    return 0;
}

C - Yet Another Broken Keyboard

#include 
#include 
#include 
#include 
#include 
#include 
#include <set>

using namespace std;

typedef long long ll;

const int N = 200010;
const int INF = 0x3f3f3f3f;

int n, k;
char s[N];
set<char> st;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d%d%s", &n, &k, s + 1);
    for (int i = 1; i <= k; i++) {
        getchar();
        char ch;
        scanf("%c", &ch);
        st.insert(ch);
    }
    ll res = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!st.count(s[i])) {
            res += cnt * (cnt + 1) / 2;
            cnt = 0;
        }
        else cnt += 1;
    }
    res += cnt * (cnt + 1) / 2;
    printf("%lld\n", res);
    return 0;
}

D - Remove One Element

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;
const int INF = 0x3f3f3f3f;

int n, a[N], dp[N][2];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    a[n + 1] = INF;
    for (int i = 1; i <= n; i++) {
        if (a[i] > a[i - 1]) dp[i][0] = dp[i - 1][0] + 1;
        else dp[i][0] = 1;
    }
    for (int i = n; i >= 1; i--) {
        if (a[i] < a[i + 1]) dp[i][1] = dp[i + 1][1] + 1;
        else dp[i][1] = 1;
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, dp[i][0]);
        if (a[i + 1] > a[i - 1]) res = max(res, dp[i - 1][0] + dp[i + 1][1]);
    }
    printf("%d\n", res);
    return 0;
}

E - Nearest Opposite Parity

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 1000010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex;
};

struct node {
    int s, w;
    node(int _s, int _w) : s(_s), w(_w) { }
    friend bool operator < (node a, node b) {
        return a.w > b.w;
    }
};

int n, cnt;
int a[N], head[N], d[N], res[N];
Edge edge[2 * N];

void init()
{
    cnt = 0;
    for (int i = 1; i <= n + 2; i++) head[i] = 0;
}

void add_edge(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

void dijkstra(int s)
{
    priority_queue q;
    for (int i = 1; i <= n + 2; i++) d[i] = INF;
    d[s] = 0;
    q.push(node(s, 0));
    while (!q.empty()) {
        node nd = q.top();
        int u = nd.s, w = nd.w;
        q.pop();
        if (w != d[u]) continue;
        for (int i = head[u]; 0 != i; i = edge[i].nex) {
            int v = edge[i].to;
            if (d[u] + 1 < d[v]) {
                d[v] = d[u] + 1;
                q.push(node(v, d[v]));
            }
        }
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    init();
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        if (0 == a[i] % 2) add_edge(n + 1, i);
        else add_edge(n + 2, i);
        if (i + a[i] <= n) add_edge(i + a[i], i);
        if (i - a[i] >= 1) add_edge(i - a[i], i);
    }
    dijkstra(n + 1);
    for (int i = 1; i <= n; i++) {
        if (0 == a[i] % 2) continue;
        res[i] = (INF == d[i] ? -1 : d[i] - 1);
    }
    dijkstra(n + 2);
    for (int i = 1; i <= n; i++) {
        if (1 == a[i] % 2) continue;
        res[i] = (INF == d[i] ? -1 : d[i] - 1);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d", res[i]);
        printf(i == n ? "\n" : " ");
    }
    return 0;
}

1463D - Pairs

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1000010;

int T, n, vis[N], a[N], b[N];

int check(int mid)
{
    for (int i = 1; i <= mid; i++)
        if (a[i] > b[n - mid + i]) return 1;
    for (int i = mid + 1; i <= n; i++)
        if (a[i] < b[i - mid]) return 2;
    return 0;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= 2 * n; i++) vis[i] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            vis[a[i]] = 1;
        }
        int cnt = 0;
        for (int i = 1; i <= 2 * n; i++) {
            if (vis[i]) continue;
            b[++cnt] = i;
        }
        int l = 0, r = n, resl = 0, resr = 0;
        while (r > l) {
            int mid = (l + r) / 2;
            if (2 != check(mid)) r = mid;
            else l = mid + 1;
        }
        resl = l;
        l = 0, r = n;
        while (r > l) {
            int mid = (l + r + 1) / 2;
            if (1 != check(mid)) l = mid;
            else r = mid - 1;
        }
        resr = l;
        printf("%d\n", resr - resl + 1);
    }
    return 0;
}

1463C - Busy Robot

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1000010;
const ll INF = 1000000000000000000;

struct node {
    ll t;
    int x;
    node() { }
    node(ll _t, int _x) : t(_t), x(_x) { }
};

int T, n;
node a[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%lld%d", &a[i].t, &a[i].x);
        a[n + 1] = node(INF, 0);
        int now = 0, ist = 0, to = 0, res = 0;
        ll stt = 0;
        for (int i = 1; i <= n; i++) {
            if (1 == ist && a[i].t - stt >= abs(now - to)) {
                ist = 0;
                now = to;
            }
            if (1 == ist) {
                if (a[i].x >= min(now, to) && a[i].x <= max(now, to)) {
                    ll tt = stt + abs(now - a[i].x);
                    if (tt >= a[i].t && tt <= a[i + 1].t) res += 1;
                }
                continue;
            }
            ist = 1;
            stt = a[i].t;
            to = a[i].x;
            if (a[i + 1].t - a[i].t >= abs(now - to)) res += 1;
        }
        printf("%d\n", res);
    }
    return 0;
}

1453C - Triangles

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2010;

int T, n;
int minr[N], maxr[N], minc[N], maxc[N];
char s[N][N];
vector<int> res;

void solve(int x)
{
    int iminr = N, imaxr = -N, iminc = N, imaxc = -N;
    for (int i = 1; i <= n; i++) {
        minr[i] = minc[i] = N;
        maxr[i] = maxc[i] = -N;
    }
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= n; k++) {
            if (x != s[i][k] - '0') continue;
            minr[i] = min(minr[i], k);
            maxr[i] = max(maxr[i], k);
            minc[k] = min(minc[k], i);
            maxc[k] = max(maxc[k], i);
            iminr = min(iminr, i);
            imaxr = max(imaxr, i);
            iminc = min(iminc, k);
            imaxc = max(imaxc, k);
        }
    }
    int imax = 0;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= n; k++) {
            if (x != s[i][k] - '0') continue;
            imax = max(imax, max(maxr[i] - k, k - minr[i]) * max(i - 1, n - i));
            imax = max(imax, max(i - minc[k], maxc[k] - i) * max(k - 1, n - k));
            imax = max(imax, max(i - iminr, imaxr - i) * max(k - 1, n - k));
            imax = max(imax, max(imaxc - k, k - iminc) * max(i - 1, n - i));
        }
    }
    res.push_back(imax);
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        res.clear();
        for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
        for (int i = 0; i <= 9; i++) solve(i);
        for (int i = 0; i <= 9; i++) {
            printf("%d", res[i]);
            printf(i == 9 ? "\n" : " ");
        }
    }
    return 0;
}

1453D - Checkpoints

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2010;

int T, a[N];
vector<int> res;
ll n;

void push(int x)
{
    res.push_back(1);
    if (1 == x) return;
    for (int i = 1; i <= x - 2; i++) res.push_back(0);
    res.push_back(1);
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        res.clear();
        int cnt = 0;
        scanf("%lld", &n);
        if (1 == n % 2) {
            printf("-1\n");
            continue;
        }
        while (n) {
            a[++cnt] = n % 2;
            n /= 2;
        }
        for (int i = 1; i <= cnt; i++) {
            if (0 == a[i]) continue;
            push(i - 1);
        }
        printf("%d\n", res.size());
        for (int i = 0; i < res.size(); i++) {
            printf("%d", res[i]);
            printf(i == res.size() - 1 ? "\n" : " ");
        }
    }
    return 0;
}

1451D - Circle Game

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int T, d, k;

int binary(int x)
{
    int l = 0, r = d + 1;
    while (r > l) {
        int mid = (l + r) / 2;
        if (1ll * x * x + 1ll * mid * mid <= 1ll * d * d) l = mid + 1;
        else r = mid;
    }
    return l;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &d, &k);
        int now = 0, f = 1, imax = 0;
        while (f) {
            int h = binary(now);
            imax = max(imax, now / k + (h + k - 1) / k);
            if (1 == f && now > d) f = 0;
            now += k;
        }
        printf(imax % 2 ? "Utkarsh\n" : "Ashish\n");
    }
    return 0;
}

1450D - Rating Compression

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 300010;
const int INF = 0x3f3f3f3f;

struct node {
    int l, r, imin;
};

int T, n, a[N], res[N];
node tr[4 * N];

void build(int k, int l, int r)
{
    tr[k].l = l;
    tr[k].r = r;
    if (l == r) {
        tr[k].imin = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * k, l, mid);
    build(2 * k + 1, mid + 1, r);
    tr[k].imin = min(tr[2 * k].imin, tr[2 * k + 1].imin);
}

int ask(int k, int a, int b)
{
    if (tr[k].l >= a && tr[k].r <= b) return tr[k].imin;
    int mid = (tr[k].l + tr[k].r) / 2, res = INF;
    if (a <= mid) res = min(res, ask(2 * k, a, b));
    if (b > mid) res = min(res, ask(2 * k + 1, a, b));
    return res;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) res[i] = 0;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        build(1, 1, n);
        int l = 1, r = n, now = 1;
        for (int i = n; i >= 1; i--) {
            if (now == ask(1, l, r)) res[i] = 1;
            else {
                res[i] = 0;
                break;
            }
            if (a[l] == now) l += 1;
            else if (a[r] == now) r -= 1;
            else break;
            now += 1;
        }
        int f = 1;
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; i++) {
            if (a[i] == a[i - 1] + 1) continue;
            f = 0;
            break;
        }
        res[1] = f;
        for (int i = 1; i <= n; i++) printf("%d", res[i]);
        printf("\n");
    }
    return 0;
}

1446B - Catching Cheaters

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 5010;

int n, m, dp[N][N];
char a[N], b[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d%d%s%s", &n, &m, a + 1, b + 1);
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= m; k++) {
            if (a[i] == b[k]) dp[i][k] = dp[i - 1][k - 1] + 2;
            else dp[i][k] = max(0, max(dp[i - 1][k], dp[i][k - 1]) - 1);
        }
    }
    int imax = 0;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= m; k++) {
            imax = max(imax, dp[i][k]);
        }
    }
    printf("%d\n", imax);
    return 0;
}

1444B - Divide and Sum

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 300010;
const ll mod = 998244353;

int n;
ll a[N], fac[N], inv[N];

ll C(int n, int m)
{
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    fac[0] = 1;
    for (int i = 1; i <= 2 * n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[1] = 1;
    for (int i = 2; i <= 2 * n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    inv[0] = 1;
    for (int i = 1; i <= 2 * n; i++) inv[i] = inv[i] * inv[i - 1] % mod;
    for (int i = 1; i <= 2 * n; i++) scanf("%lld", &a[i]);
    sort(a + 1, a + 2 * n + 1);
    ll sum = 0;
    for (int i = 1; i <= 2 * n; i++) {
        if (i <= n) sum -= a[i];
        else sum += a[i];
    }
    printf("%lld\n", sum % mod * C(2 * n, n) % mod);
    return 0;
}

1442B - Identify the Operations

#include 
#include 
#include 
#include 

using namespace std;

const int N = 200010;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;

struct node {
    int l, r, imax, imin;
};

int T, n, k;
int a[N], b[N], p[N], l[N], r[N];
node tr[4 * N];

void build(int k, int l, int r)
{
    tr[k].l = l;
    tr[k].r = r;
    tr[k].imax = 0;
    tr[k].imin = n + 1;
    if (l == r) return;
    int mid = (l + r) / 2;
    build(2 * k, l, mid);
    build(2 * k + 1, mid + 1, r);
}

void update(int k, int x, int y)
{
    if (tr[k].l == tr[k].r) {
        tr[k].imax = tr[k].imin = y;
        return;
    }
    int mid = (tr[k].l + tr[k].r) / 2;
    if (x <= mid) update(2 * k, x, y);
    else update(2 * k + 1, x, y);
    tr[k].imax = max(tr[2 * k].imax, tr[2 * k + 1].imax);
    tr[k].imin = min(tr[2 * k].imin, tr[2 * k + 1].imin);
}

int ask_max(int k, int a, int b)
{
    if (tr[k].l >= a && tr[k].r <= b) return tr[k].imax;
    int mid = (tr[k].l + tr[k].r) / 2, imax = 0;;
    if (a <= mid) imax = max(imax, ask_max(2 * k, a, b));
    if (b > mid) imax = max(imax, ask_max(2 * k + 1, a, b));
    return imax;
}

int ask_min(int k, int a, int b)
{
    if (tr[k].l >= a && tr[k].r <= b) return tr[k].imin;
    int mid = (tr[k].l + tr[k].r) / 2, imin = n + 1;
    if (a <= mid) imin = min(imin, ask_min(2 * k, a, b));
    if (b > mid) imin = min(imin, ask_min(2 * k + 1, a, b));
    return imin;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) p[i] = l[i] = r[i] = 0;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= k; i++) {
            scanf("%d", &b[k]);
            p[b[k]] = i;
        }
        build(1, 1, k);
        for (int i = 1; i <= n; i++) {
            if (0 == p[a[i]]) continue;
            int t = ask_max(1, p[a[i]] + 1, k);
            l[p[a[i]]] = i - t - 1;
            update(1, p[a[i]], i);
        }
        build(1, 1, k);
        for (int i = n; i >= 1; i--) {
            if (0 == p[a[i]]) continue;
            int t = ask_min(1, p[a[i]] + 1, k);
            r[p[a[i]]] = t - i - 1;
            update(1, p[a[i]], i);
        }
        int res = 1;
        for (int i = 1; i <= k; i++) {
            if (0 == l[i] && 0 == r[i]) res = 0;
            if (0 != l[i] && 0 != r[i]) res = res * 2 % mod;
        }
        printf("%d\n", res);
    }
    return 0;
}

1442A - Extreme Subtraction

#include 
#include 
#include 
#include 

using namespace std;

const int N = 30010;

typedef long long ll;

int T, n;
ll a[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        ll sum = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            if (a[i] - a[i - 1] < 0) sum = sum + a[i - 1] - a[i];
        }
        if (a[1] >= sum) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

1437C - Chef Monocarp

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 700;
const int M = 90010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w, c;
};

int T, n, s, t, cnt, mf, mc;
int dis[N], pre[N], lst[N], f[N];
int head[N], inq[N], ti[N];
Edge edge[2 * M];
queue<int> q;

void init()
{
    cnt = -1;
    mc = mf = 0;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, int w, int c)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].c = c;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int spfa(int s, int t)
{
    memset(dis, INF, sizeof(dis));
    memset(f, INF, sizeof(f));
    memset(inq, 0, sizeof(inq));
    while (!q.empty()) q.pop();
    q.push(s);
    inq[s] = 1, dis[s] = 0, pre[t] = -1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w, c = edge[i].c;
            if (0 == w || dis[v] <= dis[u] + c) continue;
            dis[v] = dis[u] + c;
            pre[v] = u;
            lst[v] = i;
            f[v] = min(f[u], w);
            if (1 == inq[v]) continue;
            inq[v] = 1;
            q.push(v);
        }
    }
    if (-1 == pre[t]) return 0;
    return 1;
}

void mcmf()
{
    while (spfa(s, t)) {
        mf += f[t];
        mc += f[t] * dis[t];
        int now = t;
        while (now != s) {
            edge[lst[now]].w -= f[t];
            edge[lst[now] ^ 1].w += f[t];
            now = pre[now];
        }
    }
}

void insert(int u, int v, int w, int c)
{
    add_edge(u, v, w, c);
    add_edge(v, u, 0, -c);
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &ti[i]);
        s = 3 * n + 1;
        t = 3 * n + 2;
        for (int i = 1; i <= 2 * n; i++) insert(3 * n + 1, i, 1, 0);
        for (int i = 2 * n + 1; i <= 3 * n; i++) insert(i, 3 * n + 2, 1, 0);
        for (int i = 1; i <= 2 * n; i++) {
            for (int k = 2 * n + 1; k <= 3 * n; k++) {
                insert(i, k, 1, abs(i - ti[k - 2 * n]));
            }
        }
        mcmf();
        printf("%d\n", mc);
    }
    return 0;
}

1430D - String Deletion

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;

int T, n, vis[N];
char s[N];
vector<int> v;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        v.clear();
        scanf("%d%s", &n, s + 1);
        for (int i = 0; i <= n; i++) vis[i] = 0;
        int cnt = 1, len = strlen(s + 1);
        for (int i = 2; i <= len; i++) {
            if (s[i] == s[i - 1]) cnt += 1;
            else {
                v.push_back(cnt);
                cnt = 1;
            }
        }
        v.push_back(cnt);
        int res = 0, l = 0;
        for (int i = 0; i < v.size(); i++) {
            if (v[i] >= 2) res += 1;
            else {
                while (l < v.size() && (vis[l] || 1 == v[l])) l += 1;
                if (v.size() == l) {
                    res = res + (v.size() - i + 1) / 2;
                    break;
                }
                else {
                    v[l] -= 1;
                    res += 1;
                }
            }
            vis[i] = 1;
        }
        printf("%d\n", res);
    }
    return 0;
}

1422C - Bargain

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;
const ll mod = 1000000007;

int T;
ll dp[N];
char s[N];

ll power(ll a, ll n)
{
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++) dp[i] = (dp[i - 1] + 1ll * i * power(10, i - 1) % mod) % mod;
    ll res = 0;
    for (int i = 1; i <= len; i++) {
        ll t = 1ll * i * (i - 1) / 2;
        res = (res + power(10, len - i) * (s[i] - '0') % mod * t % mod);
        res = (res + dp[len - i] * (s[i] - '0') % mod) % mod;
    }
    printf("%lld\n", res);
    return 0;
}

1426E - Rock, Paper, Scissors

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 10;
const int M = 100;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w, c;
};

int n, s, t, cnt;
int mf, mc, dis[N], f[N], a[N], b[N];
int pre[N], lst[N], head[N], inq[N];
Edge edge[2 * M];
queue<int> q;

void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v, ll w, ll c)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].c = c;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int spfa(int s, int t)
{
    memset(dis, INF, sizeof(dis));
    memset(f, INF, sizeof(f));
    memset(inq, 0, sizeof(inq));
    while (!q.empty()) q.pop();
    q.push(s);
    inq[s] = 1, dis[s] = 0, pre[t] = -1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w, c = edge[i].c;
            if (0 == w || dis[v] <= dis[u] + c) continue;
            dis[v] = dis[u] + c;
            pre[v] = u;
            lst[v] = i;
            f[v] = min(f[u], w);
            if (1 == inq[v]) continue;
            inq[v] = 1;
            q.push(v);
        }
    }
    if (-1 == pre[t]) return 0;
    return 1;
}

void mcmf()
{
    mc = mf = 0;
    while (spfa(s, t)) {
        mf += f[t];
        mc += f[t] * dis[t];
        int now = t;
        while (now != s) {
            edge[lst[now]].w -= f[t];
            edge[lst[now] ^ 1].w += f[t];
            now = pre[now];
        }
    }
}

void insert(int u, int v, int w, int c)
{
    add_edge(u, v, w, c);
    add_edge(v, u, 0, -c);
}

void solve(int f)
{
    init();
    for (int i = 1; i <= 3; i++) insert(s, i, a[i], 0);
    for (int i = 1; i <= 3; i++) insert(i + 3, t, b[i], 0);
    for (int i = 1; i <= 3; i++) {
        for (int k = 1; k <= 3; k++) {
            if (1 == i && 2 == k) insert(i, 3 + k, min(a[i], b[k]), f);
            else if (2 == i && 3 == k) insert(i, 3 + k, min(a[i], b[k]), f);
            else if (3 == i && 1 == k) insert(i, 3 + k, min(a[i], b[k]), f);
            else insert(i, 3 + k, min(a[i], b[k]), 0);
        }
    }
    mcmf();
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= 3; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= 3; i++) scanf("%d", &b[i]);
    s = 7;
    t = 8;
    solve(1);
    printf("%d ", mc);
    solve(-1);
    printf("%d\n", -mc);
    return 0;
}

1436D - Bandit in a City

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;

struct Edge {
    int to, nex;
};

int n, cnt, head[N], deg[N];
Edge edge[2 * N];
ll sum[N], sz[N], a[N];

void add_edge(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

void dfs(int u, int fa)
{
    sum[u] = a[u];
    for (int i = head[u]; 0 != i; i = edge[i].nex) {
        int v = edge[i].to;
        if (v == fa) continue;
        dfs(v, u);
        sum[u] += sum[v];
        sz[u] += sz[v];
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int t;
        scanf("%d", &t);
        add_edge(t, i);
        deg[t] += 1;
    }
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) {
        if (0 != deg[i]) continue;
        sz[i] = 1;
        sum[i] = a[i];
    }
    dfs(1, -1);
    ll res = 0;
    for (int i = 1; i <= n; i++) res = max(res, (sum[i] + sz[i] - 1) / sz[i]);
    printf("%lld\n", res);
    return 0;
}

1430E - String Reversal

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;

int n;
ll sum[N];
char s[N];
queue<int> q[26];

int lowbit(int x)
{
    return x & (-x);
}

void update(int x, ll num)
{
    while (x <= n) {
        sum[x] += num;
        x += lowbit(x);
    }
}

ll ask(int x)
{
    ll res = 0;
    while (x) {
        res += sum[x];
        x -= lowbit(x);
    }
    return res;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; i++) q[s[i] - 'a'].push(i);
    reverse(s + 1, s + n + 1);
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        int t = q[s[i] - 'a'].front();
        q[s[i] - 'a'].pop();
        res = res + ask(n) - ask(t);
        update(t, 1);
    }
    printf("%lld\n", res);
    return 0;
}

1400B - RPG Protagonist

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

int T;
ll p, f, cnts, cntw, s, w;

ll solve(ll p, ll f, ll cnts, ll cntw, ll s, ll w, ll as)
{
    ll res = as, aw = min(cntw, p / w);
    res += aw;
    cntw -= aw;
    if (s > w) {
        swap(s, w);
        swap(cnts, cntw);
    }
    ll bs = min(cnts, f / s);
    res += bs;
    f -= s * bs;
    ll bw = min(cntw, f / w);
    res += bw;
    f -= w * bw;
    return res;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%lld%lld%lld%lld", &p, &f, &cnts, &cntw, &s, &w);
        ll res = 0;
        for (ll i = 0; i <= cnts; i++) {
            if (i * s > p) continue;
            res = max(res, solve(p - i * s, f, cnts - i, cntw, s, w, i));
        }
        printf("%lld\n", res);
    }
    return 0;
}

1396B - Stoned Game

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 110;

int T, n, a[N];
priority_queue<int> q;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        while (!q.empty()) q.pop();
        scanf("%d", &n);
        int sum = 0, imax = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            sum += a[i];
            q.push(a[i]);
        }
        int now = 1, lst = 0;
        while (!q.empty()) {
            int t = q.top();
            q.pop();
            if (2 * t > sum) break;
            if (lst > 0) q.push(lst);
            sum -= 1;
            lst = t - 1;
            now = 1 - now;
        }
        if (now) printf("T\n");
        else printf("HL\n");
    }
    return 0;
}

1368D - AND, OR and square sum

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;
const ll INF = 1000000000000000000;

int n, id, c[30];
ll a[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        for (int k = 20; k >= 0; k--)
            if ((a[i] >> k) & 1) c[k] += 1;
    }
    for (int i = 1; i <= n; i++) a[i] = 0;
    for (int i = 20; i >= 0; i--) {
        for (int k = 1; k <= c[i]; k++) a[k] += (1ll << i);
    }
    ll res = 0;
    for (int i = 1; i <= n; i++) res = res + a[i] * a[i];
    printf("%lld\n", res);
    return 0;
}

1359C - Mixing Water

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;
const ll INF = 0x3f3f3f3f;
const double eps = 1e-5;

int T;
ll h, c, t;

double f(ll x, ll y)
{
    double s = 1.0 * (h * x + c * y) / (x + y);
    return fabs(1.0 * t - s);
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%lld", &h, &c, &t);
        if (h + c >= 2 * t) {
            printf("2\n");
            continue;
        }
        ll l = 0, r = INF;
        while (r > l) {
            ll lmid = l + (r - l) / 3;
            ll rmid = r - (r - l) / 3;
            if (f(lmid + 1, lmid) <= f(rmid + 1, rmid)) r = rmid - 1;
            else l = lmid + 1;
        }
        printf("%lld\n", 2 * l + 1);
    }
    return 0;
}

1340B - Nastya and Scoreboard

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 2010;

int n, k, f, ok[N][N], res[N];
char s[N][10];
char t[20][10] = {
    "1110111", "0010010", "1011101", "1011011", "0111010",
    "1101011", "1101111", "1010010", "1111111", "1111011"
};

void dfs(int now, int k)
{
    if (f || k < 0) return;
    if (now == n + 1) {
        if (0 != k) return;
        for (int i = 1; i <= n; i++) printf("%d", res[i]);
        printf("\n");
        f = 1;
        return;
    }
    if (0 == ok[now][k]) return;
    for (int i = 9; i >= 0; i--) {
        int yes = 1, cnt = 0;
        for (int j = 0; j < 7; j++) {
            if (t[i][j] == s[now][j]) continue;
            if ('0' == t[i][j] && '1' == s[now][j]) {
                yes = 0;
                break;
            }
            else cnt += 1;
        }
        if (0 == yes) continue;
        res[now] = i;
        dfs(now + 1, k - cnt);
    }
    if (!f) ok[now][k] = 0; 
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%s", s[i]);
    for (int i = 0; i <= max(n, k); i++)
        for (int j = 0; j <= max(n, k); j++) ok[i][j] = 1;
    dfs(1, k);
    if (!f) printf("-1\n");
    return 0;
}

1423B - Valuable Paper

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 20010;
const int M = 200010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, nex, w;
};

Edge edge[2 * M];
int n, m, s, t, cnt;
int d[N], cur[N], head[N];
int ui[M], vi[M], di[M];
queue<int> q;

void init()
{
    cnt = -1;
    s = 2 * n + 1;
    t = 2 * n + 2;
    for (int i = 1; i <= 2 * n + 2; i++) head[i] = -1;
}

void add_edge(int u, int v, int w)
{
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

int dfs(int u, int dist)
{
    if (u == t) return dist;
    for (int &i = cur[u]; -1 != i; i = edge[i].nex) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && d[v] == d[u] + 1) {
            int di = dfs(v, min(dist, w));
            if (di > 0) {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}

int bfs()
{
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; -1 != i; i = edge[i].nex) {
            int v = edge[i].to, w = edge[i].w;
            if (w > 0 && 0 == d[v]) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    if (d[t] > 0) return 1;
    return 0;
}

int dinic()
{
    int res = 0;
    while (bfs()) {
        for (int i = 1; i <= t; i++) cur[i] = head[i];
        while (int d = dfs(s, INF)) res += d;
    }
    return res;
}

void insert(int u, int v, int w)
{
    add_edge(u, v, w);
    add_edge(v, u, 0);
}

bool check(int mid)
{
    init();
    for (int i = 1; i <= n; i++) {
        insert(2 * n + 1, i, 1);
        insert(n + i, 2 * n + 2, 1);
    }
    for (int i = 1; i <= m; i++) {
        if (di[i] > mid) continue;
        insert(ui[i], vi[i] + n, 1);
    }
    if (dinic() == n) return true;
    return false;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &ui[i], &vi[i], &di[i]);
    int l = 0, r = INF;
    while (r > l) {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l == INF ? -1 : l);
    return 0;
}

1392D - Omkar and Bed Wars

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 200010;

int T, n;
char s[N];
vector<int> v;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        v.clear();
        scanf("%d%s", &n, s + 1);
        int cnt = 1;
        for (int i = 2; i <= n; i++) {
            if (s[i] == s[i - 1]) cnt += 1;
            else {
                v.push_back(cnt);
                cnt = 1;
            }
        }
        v.push_back(cnt);
        if (v.size() > 1 && s[1] == s[n]) {
            int sz = v.size();
            v[sz - 1] += v[0];
            v[0] = 0;
        }
        if (1 == v.size()) printf("%d\n", (v[0] + 2) / 3);
        else {
            int res = 0;
            for (int i = 0; i < v.size(); i++) res += v[i] / 3;
            printf("%d\n", res);
        }
    }
    return 0;
}

1333C - Eugene and an array

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;

int n;
ll a[N];
mapint> mp;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    ll res = 0, sum = 0;
    int pos = -1;
    mp[0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        sum += a[i];
        if (mp.count(sum)) pos = max(pos, mp[sum]);
        mp[sum] = i;
        res = res + i - pos - 1;
    }
    printf("%lld\n", res);
    return 0;
}

Codeforces Round #697 (Div. 3)

A - Odd Divisor

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;
const int INF = 0x3f3f3f3f;

int T;
ll n;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%lld", &n);
        if (1 == n % 2) printf("YES\n");
        else {
            while (0 == n % 2) n /= 2;
            if (n > 1) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

B - New Year's Number

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;
const int INF = 0x3f3f3f3f;

int T, n;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int a = n / 2020, b = n % 2020;
        if (b <= a) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

C - Ball in Berland

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;
const int INF = 0x3f3f3f3f;

int T, a, b, d[N];
ll k, c[N], res;

void solve(int len)
{
    for (int i = 1; i <= len; i++) c[i] = 0;
    for (int i = 1; i <= k; i++) {
        scanf("%d", &d[i]);
        c[d[i]] += 1;
    }
    for (int i = 1; i <= len; i++) res -= c[i] * (c[i] - 1) / 2;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%lld", &a, &b, &k);
        res = k * (k - 1) / 2;
        solve(a);
        solve(b);
        printf("%lld\n", res);
    }
    return 0;
}

D - Cleaning the Phone

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;
const int INF = 0x3f3f3f3f;

struct node {
    ll a;
    int b;
};

int T, n;
ll m, s[N], ss[N];
node nd[N];
vector v, vv;

bool cmp(node ta, node tb)
{
    return ta.a > tb.a;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        v.clear();
        vv.clear();
        scanf("%d%lld", &n, &m);
        ll sum = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &nd[i].a);
            sum += nd[i].a;
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &nd[i].b);
            if (1 == nd[i].b) v.push_back(nd[i]);
            else vv.push_back(nd[i]);
        }
        if (sum < m) {
            printf("-1\n");
            continue;
        }
        sort(v.begin(), v.end(), cmp);
        sort(vv.begin(), vv.end(), cmp);
        for (int i = 1; i <= v.size(); i++) s[i] = s[i - 1] + v[i - 1].a;
        for (int i = 1; i <= vv.size(); i++) ss[i] = ss[i - 1] + vv[i - 1].a;
        int res = INF;
        for (int i = 0; i <= v.size(); i++) {
            if (m - s[i] <= 0) {
                res = min(res, i);
                continue;
            }
            if (m - s[i] > ss[vv.size()]) continue;
            int l = 1, r = vv.size();
            while (r > l) {
                int mid = (l + r) / 2;
                if (ss[mid] >= m - s[i]) r = mid;
                else l = mid + 1;
            }
            res = min(res, i + 2 * l);
        }
        printf("%d\n", res);
    }
    return 0;
}

E - Advertising Agency

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 10010;
const ll mod = 1000000007;

int T, n, k, a[N];
ll fac[N], inv[N];

void init()
{
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[1] = 1;
    for (int i = 2; i < N; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    inv[0] = 1;
    for (int i = 1; i < N; i++) inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    init();
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        reverse(a + 1, a + n + 1);
        int cnt = 0, num = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == a[k]) cnt += 1;
            if (a[i] == a[k] && i <= k) num += 1;
        }
        ll res = fac[cnt] * inv[num] % mod * inv[cnt - num] % mod;
        printf("%lld\n", res);
    }
    return 0;
}

F - Unusual Matrix

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 1010;
const ll mod = 1000000007;

int T, n;
char a[N][N], b[N][N];

bool check()
{
    for (int i = 1; i <= n; i++) {
        if (a[1][i] == b[1][i]) continue;
        for (int k = 1; k <= n; k++) {
            if (a[k][i] == '1') a[k][i] = '0';
            else a[k][i] = '1';
        }
    }
    for (int i = 2; i <= n; i++) {
        int f = 1;
        if (a[i][1] != b[i][1]) f = 0;
        for (int k = 2; k <= n; k++) {
            if (1 == f && a[i][k] != b[i][k]) return false;
            if (0 == f && a[i][k] == b[i][k]) return false;
        }
    }
    return true;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
        for (int i = 1; i <= n; i++) scanf("%s", b[i] + 1);
        if (check()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

G - Strange Beauty

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N = 200010;
const ll mod = 1000000007;

int T, n, a[N], c[N], dp[N];

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        for (int i = 1; i < N; i++) c[i] = dp[i] = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            c[a[i]] += 1;
        }
        for (int i = 1; i < N; i++) {
            dp[i] += c[i];
            for (int k = 2 * i; k < N; k += i) dp[k] = max(dp[k], dp[i]);
        }
        int res = 0;
        for (int i = 1; i < N; i++) res = max(res, dp[i]);
        printf("%d\n", n - res);
    }
    return 0;
}

CodeForces

Codeforces训练记录

相关

Codeforces Round 628 (Div. 2) E. Ehab's REAL Number Theory Problem

Codeforces Round #610 (Div. 2)

Codeforces Global Round 6.E题

Codeforces Round #611 (Div. 3) E题

CF1545X Codeforces Round #732

codeforces和atcoder的思维题目

Codeforces 1373F - Network Coverage（模拟网络流）

CF1481X Codeforces Round #699

CF1485X Codeforces Round #701

Educational Codeforces Round 7 F. The Sum of the k-th Powers 拉格朗日插值法

Codeforces #731 (div3) E. Air Conditioners

Codeforces Round #675

标签