結果

問題 No.318 学学学学学
ユーザー airis
提出日時 2015-12-12 01:48:05
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 219 ms / 2,000 ms
コード長 2,490 bytes
コンパイル時間 1,243 ms
コンパイル使用メモリ 101,572 KB
実行使用メモリ 27,360 KB
最終ジャッジ日時 2024-06-22 15:46:17
合計ジャッジ時間 5,001 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:113:26: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘ll’ {aka ‘long long int’} [-Wformat=]
  113 |                 printf("%d%c", seg.query(i, i+1, 0, 0, seg.n), i == N-1 ? '\n' : ' ');
      |                         ~^     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                          |              |
      |                          int            ll {aka long long int}
      |                         %lld

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <numeric>
#include <bitset>
#include <complex>
#define rep(x, to) for (int x = 0; x < (to); x++)
#define REP(x, a, to) for (int x = (a); x < (to); x++)
#define foreach(itr, x) for (typeof((x).begin()) itr = (x).begin(); itr != (x).end(); itr++)
#define EPS (1e-14)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef complex<double> Complex;
typedef vector< vector<int> > Mat;
int N;
int a[100005];
map<int, vector<int> > pool;
set<int> keys;
struct LazyPropagationSegmentTree {
    int n;
    ll lazy[500005];
    ll  dat[500005];
    void init(int m) {
        n = 1;
        while (n < m) n *= 2;
        memset(lazy, 0, sizeof(lazy));
        memset(dat, 0, sizeof(dat));
    }
    void lazy_evaluate(int k, int l, int r) {
        dat[k] = lazy[k];
        if (k < n - 1) {
            lazy[2 * k + 1] = lazy[k];
            lazy[2 * k + 2] = lazy[k];
        }
        lazy[k] = 0;
    }
    void paint(int a, int b, int x, int k, int l, int r) {
        if (lazy[k] != 0) {
            lazy_evaluate(k, l, r);
        }
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            dat[k] = x;
            if (k < n - 1) {
                lazy[2 * k + 1] = x;
                lazy[2 * k + 2] = x;
            }
            return;
        }
        int m = (l + r) / 2;
        int chl = 2 * k + 1;
        int chr = 2 * k + 2;
        paint(a, b, x, chl, l, m);
        paint(a, b, x, chr, m, r);
    }
    ll query(int a, int b, int k, int l, int r) {
        if (lazy[k] != 0) {
            lazy_evaluate(k, l, r);
        }
        if (b <= l || r <= a) return 0;
        if (a <= l && r <= b) return dat[k];
        int m = (l + r) / 2;
        int chl = 2 * k + 1;
        int chr = 2 * k + 2;
        // 足し算は特に意味ない
        return query(a, b, chl, l, m) + query(a, b, chr, m, r);
    }
};
LazyPropagationSegmentTree seg;
void solve() {
    seg.init(N);
    rep(i, N) {
        keys.insert(a[i]);
        pool[a[i]].push_back(i);
    }
#if 0
    foreach(itr, pool) {
        printf("%d: ", itr->first);
        rep(i, itr->second.size()) {
            printf("%d,", itr->second[i]);
        }
        printf("\n");
    }
#endif
    foreach(itr, keys) {
        int key = *itr;
        sort(pool[key].begin(), pool[key].end());
        int left = pool[key][0];
        int right = pool[key].back();
        seg.paint(left, right+1, key, 0, 0, seg.n);
    }
    for (int i = 0; i < N; i++) {
        printf("%d%c", seg.query(i, i+1, 0, 0, seg.n), i == N-1 ? '\n' : ' ');
    }
}
int main() {
    cin >> N;
    rep(i, N) cin >> a[i];
    solve();
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0