結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2016-09-02 04:35:28 |
言語 | C++11 (gcc 13.3.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
コンパイルメッセージ
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のべき乗のサイズ)*2size = 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+yll 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 { //その他//左の子をupdateupdate(a, b, v, k * 2 + 1, l, (l + r) / 2);//右の子をupdateupdate(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]が初めて出てくる位置irepr(i, n) first[a[i]] = i; //逆rep//a[i]が最後に出てくる位置irep(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;}