結果

問題 No.318 学学学学学
ユーザー codershifthcodershifth
提出日時 2016-05-07 11:38:52
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 215 ms / 2,000 ms
コード長 3,210 bytes
コンパイル時間 2,090 ms
コンパイル使用メモリ 174,980 KB
実行使用メモリ 20,608 KB
最終ジャッジ日時 2024-06-22 17:47:46
合計ジャッジ時間 5,991 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
6,816 KB
testcase_01 AC 29 ms
6,940 KB
testcase_02 AC 36 ms
7,040 KB
testcase_03 AC 23 ms
6,940 KB
testcase_04 AC 30 ms
6,940 KB
testcase_05 AC 215 ms
20,480 KB
testcase_06 AC 172 ms
14,208 KB
testcase_07 AC 148 ms
12,160 KB
testcase_08 AC 117 ms
10,496 KB
testcase_09 AC 98 ms
9,216 KB
testcase_10 AC 70 ms
8,064 KB
testcase_11 AC 200 ms
20,608 KB
testcase_12 AC 137 ms
14,208 KB
testcase_13 AC 107 ms
12,288 KB
testcase_14 AC 87 ms
10,496 KB
testcase_15 AC 70 ms
9,216 KB
testcase_16 AC 56 ms
8,064 KB
testcase_17 AC 124 ms
14,336 KB
testcase_18 AC 112 ms
14,208 KB
testcase_19 AC 121 ms
14,208 KB
testcase_20 AC 54 ms
8,320 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 2 ms
6,944 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 1 ms
6,940 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 1 ms
6,940 KB
testcase_28 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;
template <typename T>
struct LazySegTree {
    std::vector<T> seg;         // 区間の総和
    std::vector<T> lazy;        // 遅延評価用
    int bottomSize;
    int calcBottomSize(int n)
    {
        int size = 1;
        while (size < n) size *= 2;
        return bottomSize=size;
    }
    void init(int n)
    {
        int sz = calcBottomSize(n);
        seg.resize(sz*2,0);
        lazy.resize(sz*2,-1);
    }
    LazySegTree(int n)
    {
        init(n);
    }
    void push(int k, int l, int r)
    {
        if (lazy[k] != -1)
        {
            seg[k] = lazy[k] * (r-l);
            if (r - l > 1)
            {
                lazy[k*2+1] = lazy[k];
                lazy[k*2+2] = lazy[k];
            }
            lazy[k] = -1;
        }
    }
    T merge(T x, T y) { return x + y; }
    void update(int a, int b, T v,
                int k, int l, int r)
    {
        push(k,l,r);
        if (r <= a || b <= l)
            return;
        if (a <= l && r <= b)
        {
            lazy[k] = v;
            push(k,l,r);
        }
        else
        {
            update(a,b,v,k*2+1,l,(l+r)/2);
            update(a,b,v,k*2+2,(l+r)/2,r);
            seg[k] = merge(seg[k*2+1],seg[k*2+2]);
        }
    }
    // 区間 [a,b) を v で塗りつぶす
    void update(int a, int b, T v)
    {
        update(a,b,v,0,0,bottomSize);
    }
    T query(int a, int b, int k, int l, int r)
    {
        push(k,l,r);
        if (r <= a || b <= l)
            return 0;
        if (a <= l && r <= b)
            return seg[k];
        T x = query(a,b,k*2+1,l,(l+r)/2);
        T y = query(a,b,k*2+2,(l+r)/2,r);
        return merge(x,y);
    }
    // 区間 [a,b) の総和を求める
    T query(int a, int b)
    {
        return query(a,b,0,0,bottomSize);
    }

};
class GakuX5
{
public:
    void solve(void)
    {
        int n;
        cin>>n;

        //
        // bi が t に置き換えられるのは bi の左右に t が存在するときなので
        // bi = max{t| l<=i<=r && t == a[l] == a[r]}
        //       t
        //
        vector<ll> a(n);
        map<ll,int> first;
        map<ll,int> last;
        LazySegTree<ll> seg(n);

        REP(i,n)
        {
            cin>>a[i];
            last[a[i]] = i;
            if (first.count(a[i]) == 0)
                first[a[i]] = i;
            seg.update(i,i+1,a[i]);
        }

        for (auto kv : first)
        {
            ll  v;
            int fst;
            tie(v,fst) = kv;

            // 対になっているものだけ update
            if (last.count(v) == 0)
                continue;
            seg.update(fst,last[v]+1,v);
        }
        REP(i,n)
        {
            cout<<seg.query(i,i+1);
            if (i != n-1)
                cout<<" ";
        }
        cout<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new GakuX5();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0