#393892 (C++14) No.919 You Are A Project Manager

提出ソース

結果

問題	No.919 You Are A Project Manager
ユーザー	sntea
提出日時	2019-10-26 03:24:48
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	102 ms / 3,000 ms
コード長	12,964 bytes
コンパイル時間	2,237 ms
コンパイル使用メモリ	184,812 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-27 17:53:43
合計ジャッジ時間	5,825 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	64 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	3 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	15 ms 5,376 KB
testcase_05	AC	16 ms 5,376 KB
testcase_06	AC	4 ms 5,376 KB
testcase_07	AC	39 ms 5,376 KB
testcase_08	AC	11 ms 5,376 KB
testcase_09	AC	8 ms 5,376 KB
testcase_10	AC	14 ms 5,376 KB
testcase_11	AC	12 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	16 ms 5,376 KB
testcase_14	AC	3 ms 5,376 KB
testcase_15	AC	6 ms 5,376 KB
testcase_16	AC	22 ms 5,376 KB
testcase_17	AC	65 ms 5,376 KB
testcase_18	AC	63 ms 5,376 KB
testcase_19	AC	64 ms 5,376 KB
testcase_20	AC	93 ms 5,376 KB
testcase_21	AC	65 ms 5,376 KB
testcase_22	AC	43 ms 5,376 KB
testcase_23	AC	41 ms 5,376 KB
testcase_24	AC	42 ms 5,376 KB
testcase_25	AC	42 ms 5,376 KB
testcase_26	AC	90 ms 5,376 KB
testcase_27	AC	79 ms 5,376 KB
testcase_28	AC	98 ms 5,376 KB
testcase_29	AC	65 ms 5,376 KB
testcase_30	AC	66 ms 5,376 KB
testcase_31	AC	64 ms 5,376 KB
testcase_32	AC	66 ms 5,376 KB
testcase_33	AC	47 ms 5,376 KB
testcase_34	AC	47 ms 5,376 KB
testcase_35	AC	101 ms 5,376 KB
testcase_36	AC	102 ms 5,376 KB
testcase_37	AC	101 ms 5,376 KB
testcase_38	AC	100 ms 5,376 KB
testcase_39	AC	3 ms 5,376 KB
testcase_40	AC	6 ms 5,376 KB
testcase_41	AC	3 ms 5,376 KB
testcase_42	AC	4 ms 5,376 KB
testcase_43	AC	4 ms 5,376 KB
testcase_44	AC	8 ms 5,376 KB
testcase_45	AC	3 ms 5,376 KB
testcase_46	AC	7 ms 5,376 KB
testcase_47	AC	42 ms 5,376 KB
testcase_48	AC	41 ms 5,376 KB
testcase_49	AC	45 ms 5,376 KB
testcase_50	AC	42 ms 5,376 KB
testcase_51	AC	39 ms 5,376 KB
testcase_52	AC	31 ms 5,376 KB
testcase_53	AC	39 ms 5,376 KB
testcase_54	AC	7 ms 5,376 KB
testcase_55	AC	2 ms 5,376 KB
testcase_56	AC	3 ms 5,376 KB
testcase_57	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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を実装するのが良さそう
};

int main() {
    const int len = 10101;
    int n;
    while(cin >> n) {
        const LL inf = 1e9 + 10;
        vector<LL> a(n);
        REP(i, n) cin >> a[i];
        REP(i, n) a[i] += inf;
        wavelet<LL, len, 32> w(n, a.data());
        LL ans = 0;
        FOR(k, 1, n + 1) {
            DEBUG(k);
            vector<LL> mv;
            vector<LL> rmv;
            {
                int p = 0;
                while(p + k <= n) {
                    mv.push_back(w.quantile(p, p + k, k / 2) - inf);
                    // DEBUG(w.quantile(p, p + k, k / 2) - inf);
                    p += k;
                }
            }
            {
                int p = n;
                while(p - k >= 0) {
                    rmv.push_back(w.quantile(p - k, p, k / 2) - inf);
                    // DEBUG(w.quantile(p - k, p, k / 2) - inf);
                    p -= k;
                }
            }
            // dpite(ALL(mv));
            // dpite(ALL(rmv));
            REP(i, SZ(mv) - 1) rmv[i+1] += rmv[i];
            REP(i, SZ(mv) - 1) chmax(rmv[i+1], rmv[i]);
            REP(i, SZ(mv) - 1) mv[i+1] += mv[i];
            REP(i, SZ(mv) - 1) chmax(mv[i+1], mv[i]);
            LL ma = max(mv.back(), rmv.back());
            REP(i, SZ(mv) - 1) {
                chmax(ma, mv[i] + rmv[SZ(mv) - i - 2]);
            }
            DEBUG(ma);
            chmax(ans, ma * k);
        }
        cout << ans << endl;
    }
}

yukicoder

結果

テストケース

ソースコード