QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#379338#8573. Slothful Secretaryucup-team1516#WA 1444ms47372kbC++175.4kb2024-04-06 17:11:112024-04-06 17:11:12

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 17:11:12]
  • 评测
  • 测评结果:WA
  • 用时:1444ms
  • 内存:47372kb
  • [2024-04-06 17:11:11]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

// 0-indexed
template <typename T> struct BIT {
    int n;
    vector<T> bit, ary;
    BIT(int n = 0) : n(n), bit(n + 1), ary(n) {}
    T operator[](int k) { return ary[k]; }
    // [0, i)
    T sum(int i) {
        T res = 0;
        for (; i > 0; i -= (i & -i)) {
            res += bit[i];
        }
        return res;
    }
    // [l, r)
    T sum(int l, int r) { return sum(r) - sum(l); }
    void add(int i, T a) {
        ary[i] += a;
        i++;
        for (; i <= n; i += (i & -i)) {
            bit[i] += a;
        }
    }
    int lower_bound(T k) { // k <= sum(res)
        if (k <= 0) return 0;
        int res = 0, i = 1;
        while ((i << 1) <= n)
            i <<= 1;
        for (; i; i >>= 1) {
            if (res + i <= n and bit[res + i] < k) {
                k -= bit[res += i];
            }
        }
        return res;
    }

    // The 2nd UC Stage 9: Qinhuangdao - I
    // 円環状で見たときに bit[i]+bit[i-1]+...+bit[j] を求める
    T sum_cyc(int i, int j) {
        if (j <= i) return sum(j, i + 1);
        else return sum(0, i + 1) + sum(j, n);
    }
    // The 2nd UC Stage 9: Qinhuangdao - I
    // 円環状で見たときに bit[i]+bit[i-1]+...+bit[j] >= k となる最近の j と左辺の総和を求める
    // 雑にlog2つ
    pair<int, T> lower_bound_cyc(int j, T k) {
        T prefix = sum(j + 1);
        if (prefix < k) {
            k -= prefix;
            int l = 0, r = n;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                T s = sum(mid, n);
                if (s >= k) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            return {l, prefix + sum(l, n)};
        } else {
            int l = 0, r = j + 1;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                T s = sum(mid, j + 1);
                if (s >= k) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            return {l, sum(l, j + 1)};
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    BIT<int> bit(n + 5);
    BIT<ll> seg(n + 5);
    set<int> sd;
    for (int i = 0; i < n; ++i) {
        bit.add(i, 1);
        seg.add(i, i);
        sd.insert(i);
    }
    vector<int> deg(n);
    for (int i = 0; i < n; ++i) {
        deg[i] = n - 1 - i;
    }
    int res = n;
    set<pair<int, int>> st;
    while (q--) {
        int x, y;
        cin >> x >> y;
        x -= 1, y -= 1;
        if (st.find({x, y}) == st.end()) {
            st.insert({x, y});
        } else {
            st.erase(st.find({x, y}));
            swap(x, y);
        }
        // deg[x] -= 1, deg[y] += 1
        vector<int> v;
        {
            auto it = sd.lower_bound(deg[x]);
            for (int i = 0; i < 2; ++i) {
                if (it == sd.end()) break;
                v.push_back(*it);
                it++;
            }
            it = sd.lower_bound(deg[x]);
            for (int i = 0; i < 2; ++i) {
                v.push_back(*it);
                if (it == sd.begin()) break;
                it--;
            }
        }
        {
            auto it = sd.lower_bound(deg[y]);
            for (int i = 0; i < 2; ++i) {
                if (it == sd.end()) break;
                v.push_back(*it);
                it++;
            }
            it = sd.lower_bound(deg[y]);
            for (int i = 0; i < 2; ++i) {
                v.push_back(*it);
                if (it == sd.begin()) break;
                it--;
            }
        }
        v.push_back(deg[x] - 1);
        v.push_back(deg[y] + 1);
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        auto check = [&](int i) -> bool {
            if (bit[i] == 0) return false;
            ll low_cnt = bit.sum(i);
            ll high_cnt = n - low_cnt;
            ll sum = (ll)(n - 1) * (ll)n / 2;
            ll low_sum = seg.sum(i);
            ll high_sum = sum - low_sum;
            //            cout << low_cnt << " " << high_cnt << " " << sum << " " << low_sum << " "
            //            << high_cnt
            //                 << endl;
            high_sum -= high_cnt * (high_cnt - 1) / 2;
            //            cout << " " << high_sum << " " << low_cnt * high_cnt << endl;
            return high_sum >= low_cnt * high_cnt;
        };
        for (int j : v)
            if (check(j)) res -= 1;
        bit.add(deg[x], -1);
        seg.add(deg[x], -deg[x]);
        if (bit[deg[x]] == 0) sd.erase(deg[x]);
        bit.add(deg[y], -1);
        seg.add(deg[y], -deg[y]);
        if (bit[deg[y]] == 0) sd.erase(deg[y]);
        deg[x] -= 1, deg[y] += 1;
        bit.add(deg[x], 1);
        seg.add(deg[x], deg[x]);
        if (bit[deg[x]] == 1) sd.insert(deg[x]);
        bit.add(deg[y], 1);
        seg.add(deg[y], deg[y]);
        if (bit[deg[y]] == 1) sd.insert(deg[y]);
        for (int j : v)
            if (check(j)) res += 1;
        cout << res << "\n";
    }
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1444ms
memory: 47372kb

input:

500000 500000
111236 111238
400537 400538
14798 14799
480138 480140
99901 99904
169041 169045
20969 20970
111098 111100
245492 245493
25296 25300
21736 21739
415491 415495
222594 222595
162236 162238
362422 362425
422694 422695
339973 339974
241678 241680
192401 192403
125627 125629
261473 261474
10...

output:

499998
499998
499998
499996
499993
499990
499990
499988
499988
499985
499982
499979
499979
499977
499974
499974
499974
499972
499970
499968
499968
499965
499965
499965
499965
499965
499965
499962
499959
499956
499953
499951
499951
499949
499946
499944
499942
499940
499938
499935
499932
499930
499927...

result:

wrong answer 6th numbers differ - expected: '499989', found: '499990'