結果

問題 No.924 紲星
ユーザー roaris
提出日時 2023-03-15 04:46:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,887 bytes
コンパイル時間 2,400 ms
コンパイル使用メモリ 210,588 KB
最終ジャッジ日時 2025-02-11 11:32:49
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

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;
    }
    
    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;
        
        vector<vector<int>> events;
        rep(i, N) events.pb({A[i], 0, i});
        rep(i, mids.size()) events.pb({mids[i][0], 1, mids[i][1]});
        sort(events.begin(), events.end());
        BIT bit(N);
        
        rep(i, events.size()) {
            if (events[i][1]==0) bit.add(events[i][2], 1);
            else {
                int l = L[events[i][2]]-1;
                int r = R[events[i][2]];
                int c = bit.acc(r)-bit.acc(l);
                if (c>=(r-l+1)/2) ok[events[i][2]] = events[i][0];
                else ng[events[i][2]] = events[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