結果

問題 No.924 紲星
ユーザー roarisroaris
提出日時 2023-03-15 04:57:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,910 ms / 4,000 ms
コード長 2,859 bytes
コンパイル時間 2,702 ms
コンパイル使用メモリ 217,512 KB
実行使用メモリ 48,248 KB
最終ジャッジ日時 2024-09-18 08:34:31
合計ジャッジ時間 33,104 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 7 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 7 ms
5,376 KB
testcase_06 AC 8 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3,771 ms
47,964 KB
testcase_09 AC 3,744 ms
48,060 KB
testcase_10 AC 3,711 ms
48,248 KB
testcase_11 AC 3,842 ms
47,844 KB
testcase_12 AC 3,910 ms
47,868 KB
testcase_13 AC 1,692 ms
23,328 KB
testcase_14 AC 1,993 ms
21,908 KB
testcase_15 AC 1,629 ms
21,244 KB
testcase_16 AC 1,380 ms
32,384 KB
testcase_17 AC 2,982 ms
32,720 KB
testcase_18 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
typedef long long ll;

struct BIT {
    int size;
    vector<ll> node;
    
    BIT(int n) {
        size = n;
        node.resize(n+1);
    }
    
    void add(int i, int x) {
        i++;
        while (i<=size) {
            node[i] += x;
            i += i&(-i);
        }
    }
    
    ll acc(int i) {
        ll s = 0ll;
        while (i>0) {
            s += node[i];
            i -= i&(-i);
        }
        return s;
    }
};

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    
    int N, Q; cin >> N >> Q;
    int A[N]; rep(i, N) cin >> A[i];
    int L[Q], R[Q]; rep(i, Q) cin >> L[i] >> R[i];
    
    int ng[Q], ok[Q];
    rep(i, Q) {
        ng[i] = -1e9+10;
        ok[i] = 1e9+10;
    }
    
    vector<vector<int>> vs;
    rep(i, N) vs.pb({A[i], i});
    sort(vs.begin(), vs.end());
    
    while (true) {
        vector<vector<int>> mids;
        bool finish = true;
        rep(i, Q) if (abs(ok[i]-ng[i])>1) {
            int mid = (ng[i]+ok[i])/2;
            mids.pb({mid, i});
            finish = false;
        }
        if (finish) break;
        
        sort(mids.begin(), mids.end());
        BIT bit(N);
        int idx = 0;
        
        rep(i, mids.size()) {
            while (idx<N && vs[idx][0]<=mids[i][0]) {
                bit.add(vs[idx][1], 1);
                idx++;
            }
            int l = L[mids[i][1]]-1;
            int r = R[mids[i][1]];
            int c = bit.acc(r)-bit.acc(l);
            if (c>=(r-l+1)/2) ok[mids[i][1]] = mids[i][0];
            else ng[mids[i][1]] = mids[i][0];
        }
    }
    
    // rep(i, Q) cout << ok[i] << endl;
    
    ll ans[Q]; fill(ans, ans+Q, 0ll);
    vector<vector<int>> events;
    rep(i, N) events.pb({A[i], 0, i});
    rep(i, Q) events.pb({ok[i], 1, i});
    sort(events.begin(), events.end());
    BIT bit1(N), bit2(N);
    
    rep(i, events.size()) {
        if (events[i][1]==0) {
            bit1.add(events[i][2], 1);
            bit2.add(events[i][2], events[i][0]);
        } else {
            int l = L[events[i][2]]-1;
            int r = R[events[i][2]];
            int c = bit1.acc(r)-bit1.acc(l);
            ll v = bit2.acc(r)-bit2.acc(l);
            ans[events[i][2]] += (ll)(events[i][0])*c-v;
        }
    }
    
    BIT bit3(N), bit4(N);
    
    for (int i=events.size()-1; i>=0; i--) {
        if (events[i][1]==0) {
            bit3.add(events[i][2], 1);
            bit4.add(events[i][2], events[i][0]);
        } else {
            int l = L[events[i][2]]-1;
            int r = R[events[i][2]];
            int c = bit3.acc(r)-bit3.acc(l);
            ll v = bit4.acc(r)-bit4.acc(l);
            ans[events[i][2]] += v-(ll)(events[i][0])*c;
        }
    }
    
    rep(i, Q) printf("%lld\n", ans[i]);
}
0