結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2016-09-02 04:35:28 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 185 ms / 2,000 ms |
コード長 | 3,728 bytes |
コンパイル時間 | 1,929 ms |
コンパイル使用メモリ | 77,444 KB |
実行使用メモリ | 17,280 KB |
最終ジャッジ日時 | 2024-06-22 17:56:26 |
合計ジャッジ時間 | 5,794 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 13 ms
5,248 KB |
testcase_01 | AC | 26 ms
6,144 KB |
testcase_02 | AC | 30 ms
6,400 KB |
testcase_03 | AC | 19 ms
5,376 KB |
testcase_04 | AC | 26 ms
6,144 KB |
testcase_05 | AC | 185 ms
17,152 KB |
testcase_06 | AC | 158 ms
12,544 KB |
testcase_07 | AC | 126 ms
11,008 KB |
testcase_08 | AC | 104 ms
9,728 KB |
testcase_09 | AC | 102 ms
8,960 KB |
testcase_10 | AC | 77 ms
8,064 KB |
testcase_11 | AC | 182 ms
17,280 KB |
testcase_12 | AC | 129 ms
12,672 KB |
testcase_13 | AC | 104 ms
11,008 KB |
testcase_14 | AC | 94 ms
9,728 KB |
testcase_15 | AC | 82 ms
8,960 KB |
testcase_16 | AC | 61 ms
7,936 KB |
testcase_17 | AC | 104 ms
12,544 KB |
testcase_18 | AC | 94 ms
12,544 KB |
testcase_19 | AC | 120 ms
12,672 KB |
testcase_20 | AC | 65 ms
7,936 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 1 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 1 ms
5,376 KB |
testcase_27 | AC | 1 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:94:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 94 | rep(i, n) scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <iostream> #include <map> #include <vector> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;i++) #define repr(i,n) for(int i=n-1;i>=0;i--) struct ST { vector<ll> seg, lazy; //seg木と遅延 int size; ST(int n) { //seg木のサイズは(nが入るような2のべき乗のサイズ)*2 size = 1; while (size < n) size *= 2; seg.resize(size * 2); lazy.resize(size * 2, -1); //-1で初期化 } //遅延評価 void push(int k, int l, int r) { if (lazy[k] != -1) { //遅延があるなら //ノードkは対応する区間の葉の総和 seg[k] = lazy[k] * (r - l); //ノードkを更新 //区間[l,r)がすべてlazy[k](=v)になるから if (r - l > 1) { //子ノードがあるなら lazy[k * 2 + 1] = lazy[k]; //ノードkの子(左)に伝搬 lazy[k * 2 + 2] = lazy[k]; //ノードkの子(右)に伝搬 } lazy[k] = -1; //ノードkは伝搬し終わった } } //x+y ll merge(ll x, ll y) { return x + y; } //[a,b)をvに //[l,r)はノードが持つ区間 void update(int a, int b, ll v, int k, int l, int r) { //ノードkに対して遅延があるかもしれない //その時ノードkは更新される push(k, l, r); if (r <= a || b <= l) return; //[a,b)がノードkの区間[l,r)と交差しない if (a <= l && r <= b) { //[a,b)がノードkを完全に含む lazy[k] = v; //ノードkの区間[l,r)はすべてvになったという情報 push(k, l, r); //子に伝搬 //ノードkを更新 } else { //その他 //左の子をupdate update(a, b, v, k * 2 + 1, l, (l + r) / 2); //右の子をupdate update(a, b, v, k * 2 + 2, (l + r) / 2, r); seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]); //ノードkを更新 } } void update(int a, int b, ll v) { update(a, b, v, 0, 0, size); } //[a,b)の総和 //[l,r)はノードが持つ区間 ll query(int a, int b, int k, int l, int r) { //ノードkに対して遅延があるかもしれない //その時ノードkは更新される push(k, l, r); if (r <= a || b <= l) return 0; //[a,b)がノードkの区間[l,r)と交差しない時0を返す if (a <= l && r <= b) return seg[k]; //[a,b)がノードkを完全に含む時そのノードの値を返す //左の子の総和 ll x = query(a, b, k * 2 + 1, l, (l + r) / 2); //右の子の総和 ll y = query(a, b, k * 2 + 2, (l + r) / 2, r); return merge(x, y);//子の和を返す } ll query(int a, int b) { return query(a, b, 0, 0, size); } }; int main() { int n; cin >> n; vector<int> a(n); rep(i, n) scanf("%d", &a[i]); map<int, int> first, last; //a[i]が初めて出てくる位置i repr(i, n) first[a[i]] = i; //逆rep //a[i]が最後に出てくる位置i rep(i, n) last[a[i]] = i; ST st(n); rep(i, n) st.update(i, i + 1, a[i]); //seg木初期化 //mapを回すときのfor文 //kvがmap(first)になって順番に処理されていく(mapはキーでsortされているのでその順番(要するに小さい順)) //firstはキー(a[i]),secondは値(i) //小さい数字から順番にその数字が出てくる最初と最後の間の範囲をその数字に更新 for (auto kv : first) { //if (last.count(kv.first)) { //map::count(x) キーxがあるかないか (これ必要なのか?) st.update(kv.second, last[kv.first] + 1, kv.first); //区間[first(=i),last+1)をa[i]に //} } rep(i, n) printf("%d ", (int)st.query(i, i + 1)); //区間[i,i+1)の値、要するにiの値 cout << endl; return 0; }