QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#250302#7627. Phonyucup-team1516WA 0ms3620kbC++176.6kb2023-11-13 02:09:362023-11-13 02:09:36

Judging History

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

  • [2023-11-13 02:09:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3620kb
  • [2023-11-13 02:09:36]
  • 提交

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;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

// 0-indexed
template<typename T>
struct BIT{
    int n;
    vector<T> bit;
    BIT (int n = 0) : n(n),bit(n+1) {}
    // [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) {
        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;
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,q; cin >> n >> q;
    ll K; cin >> K;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.rbegin(), a.rend());
    vector<ll> z(n);
    for (int i = 0; i < n; ++i) {
        z[i] = a[i]%K;
    }
    sort(z.begin(), z.end());
    z.erase(unique(z.begin(), z.end()), z.end());
    int m = z.size();

    int sz = 0;
    BIT<int> bit(m);
    vector<int> bbb(m);
    auto add = [&](int i) -> void {
        sz += 1;
        bit.add(i, 1);
        bbb[i] += 1;
    };

    vector<int> md(n);
    for (int i = 0; i < n; ++i) {
        md[i] = lower_bound(z.begin(), z.end(), a[i]%K) - z.begin();
        if (a[0]-a[i] < K) {
            add(md[i]);
        }
    }

    // bit[i]+bit[i-1]+bit[i-2]+...が初めてkを超える位置を求めたい
    // ただしiは既にcnt個使われているものとする
    // 最大値との差分を返すように設計したいねえ
    auto findKth = [&](int i, int k, int cnt) -> ll {
        if (bbb[i]-cnt >= k) return 0;
        if (sz-cnt < k) return K;

        int f = k-(bbb[i]-cnt);
        if (bit.sum(i) >= f) {
            int l = 0, r = i;
            while (r-l > 1) {
                int mid = (l+r)/2;
                if (bit.sum(mid, i) >= f) {
                    l = mid;
                }
                else {
                    r = mid;
                }
            }
            return z[i]-z[l];
        }
        else {
            f -= bit.sum(i);

            int l = 0, r = m;
            while (r-l > 1) {
                int mid = (l+r)/2;
                if (sz - bit.sum(mid) >= f) {
                    l = mid;
                }
                else {
                    r = mid;
                }
            }

            return z[i]+K-z[l];
        }
    };

    int pos = md[0];
    int cnt = 0;
    ll mx = a[0];
    __int128 nx = 0;

    auto bitsum = [&](int s, int t) -> int {
        if (t <= s) {
            return bit.sum(t, s+1);
        }
        else {
            return sz-bit.sum(s+1,t);
        }
    };

    auto calNext = [&]() -> void {
        if (sz >= n) {
            return;
        }
        else {
            ll dif = z[pos]-z[md[sz]];
            if (dif < 0) dif += K;
            nx = bitsum(pos, md[sz])-cnt;

            ll uo = mx-dif;
            nx += (__int128)(uo-a[sz]-K)/K*(__int128)sz;
        }
    };

    calNext();

    vector<pair<char,ll>> query;
    auto debug = [&]() -> void {
        cout << "debug" << endl;
        for (int i = 0; i < query.size(); ++i) {
            cout << query[i].first << " " << query[i].second << endl;
        }
        cout << "A" << endl;
        for (int i = 0; i < 18; ++i) {
            cout << a[i] << " ";
        }
        cout << endl;
        cout << "pos = " << pos << endl;
        cout << "cnt = " << cnt << endl;
        cout << "mx  = " << mx << endl;
        cout << "nx  = " << (ll)nx << endl;
    };

    while (q--) {
        char c; cin >> c;
        ll uouo; cin >> uouo;
        query.push_back({c, uouo});
        if (c == 'A') {
            int x = uouo;
            ll res;
            if (sz < x) {
                res = a[x-1];
            }
            else {
                ll dif = findKth(pos, x, cnt);
                res = mx-dif;
            }
            cout << res << "\n";
            if (res == 8230) {
                cout << x << " " << sz << endl;
                debug();
                return 0;
            }
        }
        else {
            auto update = [&]() -> void {
                if (pos) {
                    mx -= z[pos]-z[pos-1];
                    pos -= 1;
                    cnt = 0;
                }
                else {
                    mx -= z[0]-z[m-1]+K;
                    pos = m-1;
                    cnt = 0;
                }
            };

            ll t = uouo;
            while (sz < n and t >= nx) {
                t -= nx;
                mx = a[sz]+K;
                int j = md[sz];
                pos = j;
                add(j);
                cnt = bbb[j];

                calNext();
            }

            ll u = t/sz;
            mx -= u*K;
            t -= u*sz;

            if (bbb[pos]-cnt >= t) {
                cnt += t;
            }
            else {
                t -= (bbb[pos]-cnt);
                update();
//                debug();

                if (bit.sum(pos+1) <= t) {
                    t -= bit.sum(pos+1);
                    mx -= z[pos]-z.back()+K;
                    pos = m-1;
                    cnt = 0;
                }

                // (r,pos]は全消し可能
                int l = -1, r = pos;
                while (r-l > 1) {
                    int mid = (l+r)/2;
                    if (bit.sum(mid+1,pos+1) <= t) {
                        r = mid;
                    }
                    else {
                        l = mid;
                    }
                }
                t -= bit.sum(r+1,pos+1);
                mx -= z[pos]-z[r];
                pos = r;
                cnt = 0;
                assert(bbb[pos] >= t);
                cnt = t;
            }

//            debug();
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

input:

3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3

output:

3
4
-1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

5 8 8
294 928 293 392 719
A 4
C 200
A 5
C 10
A 2
C 120
A 1
A 3

output:

294
200
191
0
-2

result:

ok 5 lines

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3560kb

input:

100 100 233
5101 8001 6561 6329 6305 7745 4321 811 49 1121 3953 8054 8415 9876 6701 4097 6817 6081 495 5521 2389 2042 4721 8119 7441 7840 8001 5756 5561 129 1 5981 4801 7201 8465 7251 6945 5201 5626 3361 5741 3650 7901 2513 8637 3841 5621 9377 101 3661 5105 4241 5137 7501 5561 3581 4901 561 8721 811...

output:

6881
9161
4721
8230
1 18
debug
C 11
A 31
A 1
A 61
C 1
C 39
A 1
A
9876 9861 9421 9377 9161 9153 8977 8721 8637 8465 8433 8415 8119 8113 8081 8054 8001 8001 
pos = 32
cnt = 0
mx  = 8230
nx  = 8

result:

wrong answer 4th lines differ - expected: '8200', found: '8230'