結果

問題 No.924 紲星
コンテスト
ユーザー haruki_K
提出日時 2019-11-09 00:11:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,397 bytes
コンパイル時間 2,068 ms
コンパイル使用メモリ 185,720 KB
実行使用メモリ 484,124 KB
最終ジャッジ日時 2024-09-15 03:06:13
合計ジャッジ時間 8,279 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < int(n); i++)
#define rep1(i,n) for (int i = 1; i <= int(n); i++)
#define repR(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep1R(i,n) for (int i = int(n); i >= 1; i--)
#define loop(i,a,B) for (int i = a; i B; i++)
#define loopR(i,a,B) for (int i = a; i B; i--)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#ifdef LOCAL
#define dump(...) cerr << "[" << __LINE__ << ":" << __FUNCTION__ << "] ", my_dmp(#__VA_ARGS__, __VA_ARGS__)
#define say(x) cerr << "[" << __LINE__ << ":" << __FUNCTION__ << "] " << x << endl;
#define debug if (1)
void my_dmp(const char*) { cerr << endl; }
template <class T, class... U> void my_dmp(const char *s, T const& x, U const& ...y) { const char *o = "({[", *e = "]})"; for (int i = 0; *s != '\0'; cerr << *s++) { if (count(o,o+3,*s)) i++; if (count(e,e+3,*s)) i--; if (!i && *s == ',') break; } cerr << " = " << x; if (*s == ',') cerr << ", ", s++; my_dmp(s, y...); }
#else
#define dump(...)
#define say(x)
#define debug if (0)
#endif
using ll = long long;
using ld = long double;
#define int ll
#define double ld
template <class T> using pque_max = priority_queue<T>;
template <class T> using pque_min = priority_queue<T, vector<T>, greater<T> >;
template <class T, class = typename T::iterator, class = typename enable_if<!is_same<T, string>::value>::type>
ostream& operator<<(ostream& os, T const& v) { os << "{"; for (auto const& x : v) os << " " << x; return os << " }"; }
template <class T> istream& operator>>(istream& is, vector<T>& v) { for (auto& x : v) is >> x; return is; }
template <class T, class S> ostream& operator<<(ostream& os, pair<T,S> const& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template <class T, class S> istream& operator>>(istream& is, pair<T,S>& p) { return is >> p.first >> p.second; }
struct my_Init { my_Init() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } my_init;

template <class T, size_t d, class = typename enable_if<(d == 0)>::type> constexpr auto make_v(T const& x = {}) { return x; }
template <class T, size_t d, class... U, class = typename enable_if<(d > 0)>::type> constexpr auto make_v(size_t n, U... x) { auto val = make_v<T,d-1>(x...); return vector<decltype(val)>(n, move(val)); }
template <class T> void quit(T const& x) { cout << x << endl; exit(0); }
template <class T> constexpr bool chmin(T& x, T const& y) { if (x > y) { x = y; return true; } return false; }
template <class T> constexpr bool chmax(T& x, T const& y) { if (x < y) { x = y; return true; } return false; }
template <class It> constexpr auto sumof(It b, It e) { return accumulate(b,e,typename iterator_traits<It>::value_type{}); }
const ll INF = (1LL<<62)-1; // ~ 4.6e18
////////////////////////////////
//
template <class T>
struct Compress {
    vector<T> v;
    bool ok = false;
    void add(T const& x) { v.push_back(x); }
    template <class It>
    void add(It f, It l) { copy(f,l,back_inserter(v)); }
    void init() { sort(all(v)); v.erase(unique(all(v)), v.end()); ok = true; }
    int size() const { return v.size(); }
    T operator[](int i) const { assert(ok); return v[i]; }
    int find(T const& x) const { assert(ok); return lower_bound(all(v),x)-v.begin(); }
};
//
const int B = 500*2;
int n,q,m;
vector<int> a,sa,b;
Compress<int> X;
vector<vector<int> > c;
vector<vector<int32_t> > d;

int32_t main() {
    cin >> n >> q;
    m = (n+B-1)/B;
    a = vector<int>(m*B);
    rep (i,n) cin >> a[i];
    int n_old = n;
    n = m*B;
    sa.resize(n+1);
    rep (i,n) sa[i+1] = sa[i] + a[i];
    dump(n,m);
    dump(vector<int>(sa.begin(),sa.begin()+n_old));

    X.add(-INF), X.add(+INF);
    rep (i,n) X.add(a[i]);
    X.init();
    b = vector<int>(n);
    rep (i,n) b[i] = X.find(a[i]);
    dump(vector<int>(b.begin(),b.begin()+n_old));
    dump(X.v);

    c.resize(m); rep (i,m) c[i].resize(X.size());
    d.resize(m); rep (i,m) d[i].resize(X.size());
    rep (i,m) {
        int l = i*B, r = (i+1)*B;
        loop (j,l,<r) {
            c[i][b[j]] += a[j];
            d[i][b[j]]++;
        }
        rep (j,X.size()-1) {
            c[i][j+1] += c[i][j];
            d[i][j+1] += d[i][j];
        }
    }
    dump(c);
    dump(d);

    auto cc = [&](int r, int m) {
        int sum = 0;
        rep (i,r/B) sum += c[i][m];
        loop (i,(r/B)*B,<r) if (b[i] <= m) sum += a[i];
        return sum;
    };
    auto dd = [&](int r, int m) {
        int sum = 0;
        rep (i,r/B) sum += d[i][m];
        loop (i,(r/B)*B,<r) if (b[i] <= m) sum++;
        return sum;
    };
    debug {
        int m = 3;
        dump(m,X[m]);
        rep (i,n_old+1) {
            dump(i,cc(i,m),dd(i,m));
        }
    }

    while (q--) {
        int l,r; cin >> l >> r; l--;
//        dump(l,r);
        int x = 0, y = X.size()-1;
        while (x+1 < y) {
            int m = (x+y)/2;
            int cnt = dd(r,m)-dd(l,m);
//            dump(m,X[m],cnt);
            ((r-l+1)/2 <= cnt ? y : x) = m;
        }
        int m = y;
//        dump(m,X[m]);
        int ans = sa[r]-sa[l]-(r-l)*X[m]
            - 2*( (cc(r,m)-cc(l,m)) - (dd(r,m)-dd(l,m))*X[m] );
//        dump(sa[r]-sa[l],(r-l)*X[m], (cc(r,m)-cc(l,m)),  (dd(r,m)-dd(l,m))*X[m] );
        cout << ans << "\n";
    }
}
0