#64624 (C++11（廃止可能性あり）) No.318 学学学学学

• 問題: No.318 学学学学学
• ユーザー: hirokazu1020
• 提出日時: 2015-12-11 00:17:02
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 119 ms / 2,000 ms
• コード長: 1,756 bytes
• コンパイル時間: 972 ms
• コンパイル使用メモリ: 98,116 KB
• 実行使用メモリ: 11,648 KB
• 最終ジャッジ日時: 2024-06-22 14:34:49
• 合計ジャッジ時間: 4,082 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 26

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#define _CRT_SECURE_NO_WARNINGS
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())
#define indexOf(v,x) (find(all(v),x)-v.begin())
class RangeSubstituteTree {//範囲代入
    int n, t;
    std::vector<int> ts, val;
    void substitute(int a, int b, int x, int k, int l, int r) {
        if (r <= a || b <= l)return;
        if (a <= l && r <= b) {
            ts[k] = t;
            val[k] = x;
            return;
        }
        int m = (l + r) / 2;
        substitute(a, b, x, 2 * k + 1, l, m);
        substitute(a, b, x, 2 * k + 2, m, r);
    }
public:
    RangeSubstituteTree(int n = 1 << 20) :n(n) {
        ts.assign(2 * n - 1, t = 0);
        val.assign(2 * n - 1, 0);
    }
    void substitute(int a, int b, int x) {//[a,b)にxを代入
        t++;
        substitute(a, b, x, 0, 0, n);
    }
    int get(int k)const {//k番目の値
        int res, s;
        k += n - 1;
        res = val[k];
        s = ts[k];
        while (k>0) {
            k = (k - 1) / 2;
            if (s<ts[k]) {
                s = ts[k];
                res = val[k];
            }
        }
        return res;
    }
};
int main() {
    map<int, pair<int, int>> idxs;
    int n;
    cin >> n;
    rep(i,n) {
        int a;
        cin >> a;
        if (idxs.find(a) == idxs.end()) {
            idxs[a] = make_pair(i,i);
        }
        else {
            idxs[a].second = i;
        }
    }
    RangeSubstituteTree rst(1<<17);
    for (auto p:idxs) {
        rst.substitute(p.second.first, p.second.second + 1, p.first);
    }
    
    rep(i,n-1) {
        cout << rst.get(i) << ' ';
    }
    cout << rst.get(n - 1) << endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX