QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#249183#7627. Phonyucup-team1516#WA 0ms3760kbC++176.5kb2023-11-12 01:51:172023-11-12 01:51:18

Judging History

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

  • [2023-11-12 01:51:18]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3760kb
  • [2023-11-12 01:51:17]
  • 提交

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;
//    n = myRand(1000)+1, q = myRand(10000)+1;
    ll K;
//    K = myRand(1000)+1;
    cin >> K;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
//        a[i] = myRand(100);
    }
    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 {
            // cntは0になっているはず
            // 追加した直後なので

            ll dif = z[pos]-z[md[sz]];
            if (dif < 0) dif += K;
            nx = bitsum(pos, md[sz]);

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

    calNext();

    auto debug = [&]() -> void {
        cout << "bbb" << endl;
        for (int i = 0; i < m; ++i) {
            cout << bbb[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;
//        if (myRand(2) == 0) {
//            c = 'A';
//        }
//        else {
//            c = 'C';
//        }
//        ll uouo = myRand(n)+1;
        ll uouo; cin >> uouo;
        if (c == 'A') {
            int x = uouo;
            if (sz < x) {
                cout << a[x-1] << "\n";
            }
            else {
                ll dif = findKth(pos, x, cnt);
                cout << mx-dif << "\n";
            }
        }
        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;
                pos = md[sz];
                add(md[sz]);

                update();
                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();
        }
    }
}

詳細信息

Test #1:

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

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: 3600kb

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: 3760kb

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
2945
7734
7556
5291
5001
2042
4721
4721
6881
4097
7302
7324
7149
7208
811
6945
2561
6945
6442
6503
3581
5291
1485
6302
6135
2042
6053
6115
6159
4721
6013
4029
4097
4901
5789
4721
5649
2042
5649
5521
5692
5482
3581
5393
115
2042
5328
2042
5328
1485
5386
-16686

result:

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