結果
| 問題 | No.924 紲星 |
| ユーザー |
 sntea
|
| 提出日時 | 2019-11-18 23:52:50 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 607 ms / 4,000 ms |
| コード長 | 13,486 bytes |
| コンパイル時間 | 2,510 ms |
| コンパイル使用メモリ | 197,008 KB |
| 実行使用メモリ | 38,528 KB |
| 最終ジャッジ日時 | 2024-10-02 14:08:11 |
| 合計ジャッジ時間 | 10,181 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 13 ms
8,832 KB |
| testcase_01 | AC | 12 ms
8,832 KB |
| testcase_02 | AC | 12 ms
8,576 KB |
| testcase_03 | AC | 12 ms
8,832 KB |
| testcase_04 | AC | 13 ms
8,704 KB |
| testcase_05 | AC | 14 ms
8,704 KB |
| testcase_06 | AC | 13 ms
8,704 KB |
| testcase_07 | AC | 14 ms
8,704 KB |
| testcase_08 | AC | 603 ms
38,528 KB |
| testcase_09 | AC | 602 ms
38,528 KB |
| testcase_10 | AC | 607 ms
38,528 KB |
| testcase_11 | AC | 574 ms
38,528 KB |
| testcase_12 | AC | 601 ms
38,528 KB |
| testcase_13 | AC | 257 ms
21,248 KB |
| testcase_14 | AC | 240 ms
18,944 KB |
| testcase_15 | AC | 224 ms
19,456 KB |
| testcase_16 | AC | 259 ms
27,776 KB |
| testcase_17 | AC | 368 ms
24,064 KB |
| testcase_18 | AC | 12 ms
8,576 KB |
ソースコード
#ifdef LOCAL111
#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize ("O3")
#define NDEBUG
#endif
// #define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { os << '(' << p.first << ' ' << p.second << ')'; return os; }
#define endl '\n'
#define ALL(a) (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
#define DEBUG(x) true
template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
for(auto &e:u) fill_v<T>(e,v...);
}
const array<int, 4> dx = {0, 1, 0, -1};
const array<int, 4> dy = {1, 0, -1, 0};
typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;
void ios_init(){
//cout.setf(ios::fixed);
//cout.precision(12);
#ifdef LOCAL111
return;
#endif
ios::sync_with_stdio(false); cin.tie(0);
}
/*****************/
// Dictionary
/*****************/
// Nはバケット数
template<int N> class FID {
static const int bucket = 512, block = 16;
// 整数iのpopcountをO(1)で求めるためのテーブル
// popcount[i] = __builtin_popcount(i), i<65536
static char popcount[];
// B[i]: s[0:512*i)のビット1の総数
int n, B[N/bucket+10];
// bs[i]: s[16*i:16*(i+1)]のビット列そのもの
unsigned short bs[N/block+10] = {};
// b[i]: s[i/32*512:i/32*512+i%32*32)のビット1の総数
// bs[i]を512bitずつリセットしながら、累積和を取ってる感じ。
unsigned short b[N/block+10] = {};
public:
FID(){}
FID(int n, bool s[]) : n(n) {
if(!popcount[1]) for (int i = 0; i < (1<<block); i++) popcount[i] = __builtin_popcount(i);
bs[0] = B[0] = b[0] = 0;
for (int i = 0; i < n; i++) {
if(i%block == 0) {
bs[i/block+1] = 0;
if(i%bucket == 0) {
B[i/bucket+1] = B[i/bucket];
b[i/block+1] = b[i/block] = 0;
}
else b[i/block+1] = b[i/block];
}
bs[i/block] |= short(s[i])<<(i%block);
b[i/block+1] += s[i];
B[i/bucket+1] += s[i];
}
if(n%bucket == 0) b[n/block] = 0;
}
// number of val in [0,r), O(1)
// 大ブロックの累積和(512bit)+中ブロックの累積和(16bit)+「余り分に適切なbitmaskをかけてpopcount」
int count(bool val, int r) { return val? B[r/bucket]+b[r/block]+popcount[bs[r/block]&((1<<(r%block))-1)]: r-count(1,r); }
// number of val in [l,r), O(1)
int count(bool val, int l, int r) { return count(val,r)-count(val,l); }
// position of ith in val, 0-indexed, O(log n)
// 範囲外を示していたら-1を返す
int select(bool val, int i) {
if(i < 0 or count(val,n) <= i) return -1;
i++;
int lb = 0, ub = n, md;
while(ub-lb>1) {
md = (lb+ub)>>1;
if(count(val,md) >= i) ub = md;
else lb = md;
}
return ub-1;
}
int select(bool val, int i, int l) { return select(val,i+count(val,l)); }
bool operator[](int i) { return bs[i/block]>>(i%block)&1; }
void print(void) {
/*
REP(i, 1+(N-1)/bucket) {
cout << B[i] << " ";
}
cout << endl;
REP(i, 1+(N-1)/block) {
cout << b[i] << " ";
}
cout << endl;
*/
REP(i, 1+(N-1)/block) {
cout << bits_to_string(bs[i], (i != (N-1)/block ? 16 : N - (N-1)/block*block)) << " ";
}
cout << endl;
}
};
template<int N> char FID<N>::popcount[1<<FID<N>::block];
/*****************/
// Wavelet Matrix
/*****************/
// 長さNで、値域[0, m=2^D)の整数を管理する
#define ENABLE_SUM
template<class T, int N, int D> class wavelet {
int n, zs[D];
FID<N> dat[D];
public:
wavelet(int n, T seq[]) : n(n) {
T f[N], l[N], r[N];
bool b[N];
memcpy(f, seq, sizeof(T)*n);
for (int d = 0; d < D; d++) {
int lh = 0, rh = 0;
for (int i = 0; i < n; i++) {
bool k = (f[i]>>(D-d-1))&1;
if(k) r[rh++] = f[i];
else l[lh++] = f[i];
b[i] = k;
}
dat[d] = FID<N>(n,b);
zs[d] = lh;
swap(l,f);
memcpy(f+lh, r, rh*sizeof(T));
}
}
void print(void) {
REP(i, D) cout << zs[i] << " "; cout << endl;
REP(i, D) dat[i].print();
}
// get, []: i番目の要素
// O(1)
T get(int i) {
T ret = 0;
bool b;
for (int d = 0; d < D; d++) {
ret <<= 1;
b = dat[d][i];
ret |= b;
i = dat[d].count(b,i)+b*zs[d];
}
return ret;
}
T operator[](int i) { return get(i); }
// rank: 区間[0,r)にあるvalの個数
// O(log m)
int count(T val, int l, int r) {
for (int d = 0; d < D; d++) {
// ここで[l, r)にxのd桁目までが全て入っていることを保証(d>0)
bool b = (val>>(D-d-1))&1;
l = dat[d].count(b,l)+b*zs[d];
r = dat[d].count(b,r)+b*zs[d];
}
return r-l;
}
int count(T val, int r) { return count(val,0,r); }
// select: i番目のvalの位置
// O(log m log log m)
int select(T val, int k) {
int ls[D], rs[D], l = 0, r = n;
for (int d = 0; d < D; d++) {
ls[d] = l; rs[d] = r;
bool b = val>>(D-d-1)&1;
l = dat[d].count(b,l)+b*zs[d];
r = dat[d].count(b,r)+b*zs[d];
}
for (int d = D-1; d >= 0; d--) {
bool b = val>>(D-d-1)&1;
k = dat[d].select(b,k,ls[d]);
if(k >= rs[d] or k < 0) return -1;
k -= ls[d];
}
return k;
}
int select(T val, int k, int l) { return select(val,k+count(val,l)); }
// maximum: 区間[l,r)で大きい順にk個
// O(k log m)
void list_max_dfs(int d, int l, int r, int &k, T val, vector<T> &vs) {
if(l >= r or !k) return;
if(d == D) {
while(l++ < r and k > 0) vs.push_back(val), k--;
return;
}
int lc = dat[d].count(1,l), rc = dat[d].count(1,r);
// if min, change this order
list_max_dfs(d+1, lc+zs[d], rc+zs[d], k, 1ULL<<(D-d-1)|val,vs);
list_max_dfs(d+1, l-lc, r-rc, k, val, vs);
}
vector<T> list_max(int l, int r, int k) {
if (r-l < k) k = r-l;
if(k < 0) return {};
vector<T> ret;
list_max_dfs(0,l,r,k,0,ret);
return ret;
}
// 添字[l, r)の要素で、値が[a, b)のもののうち最大値を求める
// valは上からd bit決めて他0を埋めた時の値。
//
// O(log m)
T rangemax_dfs(int d, int l, int r, T val, T a, T b) {
if(r-l <= 0 or val >= b) return -1;
if(d == D) return val>=a? val: -1;
int lc = dat[d].count(1,l), rc = dat[d].count(1,r);
T ret = rangemax_dfs(d+1, lc+zs[d], rc+zs[d], 1ULL<<(D-d-1)|val, a, b);
if(~ret) return ret; // 1側を見て見つかったならそれに越したことはない
return rangemax_dfs(d+1, l-lc, r-rc, val, a, b); // なければ0側を見る
}
T rangemax(int l, int r, T a, T b) { return rangemax_dfs(0,l,r,0,a,b); }
// k is 0-indexed!!!!
// quantile: 区間[l,r)でk番目に大きい数
// O(log m)
T quantile(int l, int r, int k) {
if(r-l <= k or k < 0) return -1;
T ret = 0;
for (int d = 0; d < D; d++) {
int lc = dat[d].count(1,l), rc = dat[d].count(1,r);
// lc - rc = [l, r)で立っている1の数
if(rc-lc > k) { // 1の数にkが収まっていれば
l = lc+zs[d], r = rc+zs[d]; // 1側に遷移
ret |= 1ULL<<(D-d-1);
} else { // 0側ならば
k -= rc-lc; // 1側にあった数だけkを削って次へ
l -= lc, r -= rc;
}
}
return ret;
}
T min(int l, int r) { return quantile(l, r, 0); }
T max(int l, int r) { return quantile(l, r, r-l-1); }
// freq_list: 区間[l,r)で値が[lb,ub)になる値とその出現回数の組のリスト
// O(k log m), kはヒット数
void list_freq_dfs(int d, int l, int r, T val, T a, T b, vector<pair<T,int>> &vs) {
if(val >= b or r-l <= 0) return;
if(d == D) {
if(a <= val) vs.push_back(make_pair(val,r-l));
return;
}
T nv = val|(1LL<<(D-d-1)), nnv = nv|(((1LL<<(D-d-1))-1));
if(nnv < a) return;
int lc = dat[d].count(1,l), rc = dat[d].count(1,r);
list_freq_dfs(d+1,l-lc,r-rc,val,a,b,vs);
list_freq_dfs(d+1,lc+zs[d],rc+zs[d],nv,a,b,vs);
}
vector<pair<T,int>> list_freq(int l, int r, T a, T b) {
vector<pair<T,int>> ret;
list_freq_dfs(0,l,r,0,a,b,ret);
return ret;
}
// get_rect: 区間[l,r)で値が[lb,ub)になる要素の位置とその値の組(つまり矩形内にある点の座標)のリスト
// O(k log m), kはヒット数
vector<pair<int,T>> get_rect(int l, int r, T a, T b) {
vector<pair<T,int>> res = list_freq(l,r,a,b);
vector<pair<int,T>> ret;
for(auto &e: res)
for (int i = 0; i < e.second; i++)
ret.push_back(make_pair(select(e.first,i,l), e.first));
return ret;
}
// number of elements in [l,r) in [a,b)
// O(log m)
LL freq_dfs(int d, int l, int r, T val, T a, T b) {
if(l == r) return 0;
if(d == D) return (a <= val and val < b)? r-l: 0;
T nv = 1ULL<<(D-d-1)|val, nnv = ((1ULL<<(D-d-1))-1)|nv;
if(nnv < a or b <= val) return 0;
if(a <= val and nnv < b) return r-l;
int lc = dat[d].count(1,l), rc = dat[d].count(1,r);
return freq_dfs(d+1,l-lc,r-rc,val,a,b)+
freq_dfs(d+1,lc+zs[d],rc+zs[d],nv,a,b);
}
LL freq(int l, int r, T a, T b) { return freq_dfs(0,l,r,0,a,b); }
// TODO
// 普通に
// https://www.slideshare.net/pfi/ss-15916040
// rangemaxk, rangemink, prevvalue, nextvalue, intersectを実装するのが良さそう
};
template<typename T>
class BIT {
private:
int n;
vector<T> dat;
T init;
public:
BIT(int x){
n = x;
init = 0; //書き換えする
dat = vector<T>(n+1);
for(int i = 0; i < n+1; i++){
dat[i] = init;
}
return;
}
inline T func(T x, T y){
return x+y; //書き換えする
}
T query(int i){ //[0,i)へのクエリ
T s = 0;
while(i > 0){
s = func(s, dat[i]);
i -= i&-i;
}
return s;
}
void add(int i, T x){
i++;
while(i <= n){
dat[i] = func(dat[i],x);
i += i & -i;
}
}
};
int main()
{
ios_init();
int n, q;
while(cin >> n >> q) {
const LL D = 1e10;
const LL len = 2e5 + 100;
vector<LL> a(n);
REP(i, n) cin >> a[i];
auto at = a;
REP(i, n) at[i] += D;
vector<int> l(q), r(q);
REP(i, q) {
cin >> l[i] >> r[i];
l[i]--;
}
vector<LL> med(q);
wavelet<LL, len, 40> wa(SZ(at), at.data());
REP(i, q) {
med[i] = wa.quantile(l[i], r[i], (r[i] - l[i]) / 2) - D;
}
dpite(ALL(med));
vector<vector<int>> ad(n + 1);
vector<vector<int>> rm(n + 1);
REP(i, q) {
ad[l[i]].push_back(i);
rm[r[i]].push_back(i);
}
auto za = a;
sort(ALL(za));
za.erase(unique(ALL(za)), za.end());
BIT<LL> bit(SZ(za));
BIT<int> cnt(SZ(za));
vector<LL> ans(q);
LL sum = 0;
// LL num = 0;
REP(i, n + 1) {
DEBUG(i);
for(auto&& ae : ad[i]) {
int bo = lower_bound(ALL(za), med[ae]) - za.begin();
LL s = bit.query(bo);
LL c = cnt.query(bo);
LL val = - s + (sum - s) + c * med[ae] - (i + 1 - c) * med[ae];
ans[ae] -= val;
}
for(auto&& re : rm[i]) {
int bo = lower_bound(ALL(za), med[re]) - za.begin();
LL s = bit.query(bo);
LL c = cnt.query(bo);
LL val = - s + (sum - s) + c * med[re] - (i + 1 - c) * med[re];
ans[re] += val;
}
dpite(ALL(ans));
if(i != n) {
int k = lower_bound(ALL(za), a[i]) - za.begin();
bit.add(k, a[i]);
cnt.add(k, 1);
sum += a[i];
}
}
REP(i, q) {
cout << ans[i] << endl;
}
}
return 0;
}