SCPC 2024 Round 1 코드 투척

/**
 *    author:  pizzaroot
 *    created: 2024-07-06 11:49:53
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        cout << "Case #" << tc << '\n';
        int n; string s; cin >> n >> s;
        int ans = 0, cur = -1;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'A') {
                if (cur != -1) ans += max(0, 3 - i + cur);
                cur = i;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

/**
 *    author:  pizzaroot
 *    created: 2024-07-06 12:08:15
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        cout << "Case #" << tc << '\n';
        int n; cin >> n; vi a(n);
        for (auto &x: a) cin >> x;
        sort(all(a));
        cout << 2 * (accumulate(a.begin() + n / 4 * 3, a.end(), 0LL) - accumulate(a.begin(), a.begin() + n / 4, 0LL)) << '\n';
    }
    return 0;
}

/**
 *    author:  pizzaroot
 *    created: 2024-07-06 12:45:33
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        cout << "Case #" << tc << '\n';
        int n; cin >> n; vector<vi> adj(n + 1);
        for (int i = 0; i < n + 1; i++) {
            int a, b; cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        vi ext;
        for (int i = 1; i <= n; i++) {
            if (adj[i].size() == 3) ext.push_back(i);
        }
        ll cnt = 1, cur, prev = ext[0];
        for (auto &x: adj[ext[0]]) {
            if (x != ext[1]) cur = x;
        }
        while (cur != ext[1]) {
            for (auto &x: adj[cur]) {
                if (x == prev) continue;
                prev = cur;
                cur = x;
                cnt++;
                break;
            }
        }
        cout << cnt * (cnt - 1) / 2 + (n - cnt) * (n - cnt - 1) / 2 << '\n';
    }
    return 0;
}

/**
 *    author:  pizzaroot
 *    created: 2024-07-06 13:06:50
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
ll solve(vi A, vi B, ll N, ll L) {
    ll dap = 0; vi RS(N), LS(N), RSNXT(N), LSPRV(N);
    for (int i = 1; i < N; i++) {
        if (abs(A[i] - B[i - 1]) <= L) RS[i] = 1;
        if (abs(A[i - 1] - B[i]) <= L) LS[i - 1] = 1;
    }
    for (int i = N - 1; i >= 0; i--) {
        if (RS[i] == 0) RSNXT[i] = i;
        else if (i < N - 1) RSNXT[i] = RSNXT[i + 1];
        else RSNXT[i] = N;
    }
    for (int i = 0; i < N; i++) {
        if (LS[i] == 0) LSPRV[i] = i;
        else if (i > 0) LSPRV[i] = LSPRV[i - 1];
        else LSPRV[i] = -1;
    }
    for (int i = 0; i < N; i++) {
        ll diff = A[i] - B[i];
        dap = max(dap, abs(diff));
        ll target = A[i] + L;
        int lo = i, hi = i < N - 1 ? RSNXT[i + 1] - 1 : N - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) >> 1;
            if (B[mid] > target/* || abs(A[mid] - B[i]) > L*/) hi = mid - 1;
            else lo = mid;
        }
        dap = max(dap, abs(A[i] - B[lo]));
        // dap = max(dap, abs(A[lo] - B[i]));
        target = A[i] - L;
        lo = i > 0 ? LSPRV[i - 1] + 1 : 0, hi = i;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (B[mid] < target/* || abs(A[mid] - B[i]) > L*/) lo = mid + 1;
            else hi = mid;
        }
        dap = max(dap, abs(A[i] - B[lo]));
        // dap = max(dap, abs(A[lo] - B[i]));
    }
    return dap;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        cout << "Case #" << tc << '\n';
        int N, L; cin >> N >> L; vi A(N), B(N), C(N);
        for (auto &x: A) cin >> x;
        for (auto &x: B) cin >> x;
        sort(all(A)); sort(all(B));
        // for (auto &x: A) cout << x << ' '; cout << '\n';
        // for (auto &x: B) cout << x << ' '; cout << '\n';        

        ll dap = max(solve(A, B, N, L), solve(B, A, N, L));
        if (dap > L) cout << "-1\n";
        else cout << dap << '\n';
    }
    return 0;
}

/**
 *    author:  pizzaroot
 *    created: 2024-07-06 13:51:58
**/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        cout << "Case #" << tc << '\n';
        int n; cin >> n; vi a(n), cnt(50001);
        for (auto &x: a) cin >> x;
        int q, idx = 0; cin >> q; vector<pair<int, pi>> qs(q);
        for (auto &x: qs) {
            cin >> x.second.first >> x.second.second; x.first = idx++;
            x.second.first--; x.second.second--;
        }
        int sq = sqrt(n); vi dap(q);
        sort(all(qs), [&](const pair<int, pi> &x, const pair<int, pi> &y) {
            if (x.second.first / sq != y.second.first / sq) return x.second.first / sq < y.second.first / sq;
            return x.second.second < y.second.second;
        });
        int lo = qs[0].second.first, hi = qs[0].second.second;
        map<int, int> mp;
        ll ans = 0;
        for (int i = lo; i <= hi; i++) {
            if (a[i] > 50000 || a[i] == 1) continue;
            cnt[a[i]]++;
            ll cur = a[i];
            while (cnt[cur] % cur == 0) {
                ans++;
                if (cur * cur > 50000) break;
                cur *= cur;
                cnt[cur]++;
            }
        }
        dap[qs[0].first] = ans;
        for (int i = 1; i < q; i++) {
            while (lo < qs[i].second.first) {
                ll cur = a[lo++];
                if (cur > 50000 || cur == 1) continue;
                cnt[cur]--;
                while ((cnt[cur] + 1) % cur == 0) {
                    ans--;
                    if (cur * cur > 50000) break;
                    cur *= cur;
                    cnt[cur]--;
                }
            }
            while (lo > qs[i].second.first) {
                ll cur = a[--lo];
                if (cur > 50000 || cur == 1) continue;
                cnt[cur]++;
                while (cnt[cur] % cur == 0) {
                    ans++;
                    if (cur * cur > 50000) break;
                    cur *= cur;
                    cnt[cur]++;
                }
            }
            while (hi < qs[i].second.second) {   
                ll cur = a[++hi];
                if (cur > 50000 || cur == 1) continue;
                cnt[cur]++;
                while (cnt[cur] % cur == 0) {
                    ans++;
                    if (cur * cur > 50000) break;
                    cur *= cur;
                    cnt[cur]++;
                }
            }
            while (hi > qs[i].second.second) {
                ll cur = a[hi--];
                if (cur > 50000 || cur == 1) continue;
                cnt[cur]--;
                while ((cnt[cur] + 1) % cur == 0) {
                    ans--;
                    if (cur * cur > 50000) break;
                    cur *= cur;
                    cnt[cur]--;
                }
            }
            dap[qs[i].first] = ans;
        }
        for (auto &x: dap) cout << x << '\n';
    }
    return 0;
}