結果

問題 No.855 ヘビの日光浴
ユーザー square1001
提出日時 2020-03-02 22:00:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,102 ms / 3,153 ms
コード長 2,357 bytes
コンパイル時間 1,195 ms
コンパイル使用メモリ 94,484 KB
実行使用メモリ 168,984 KB
最終ジャッジ日時 2024-10-01 20:58:06
合計ジャッジ時間 47,470 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

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

#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
class segmenttree {
private:
    int n, sz;
    unordered_map<int, int> val;
public:
    segmenttree() : n(0), sz(0) {};
    segmenttree(int n_) : n(n_) {
        sz = 1;
        while (sz < n) sz *= 2;
    }
    void update(int pos, int x) {
        pos += sz;
        val[pos] = x;
        while (pos > 1) {
            pos >>= 1;
            val[pos] = max(val[pos * 2], val[pos * 2 + 1]);
        }
    }
    int reachl(int x) {
        if (val[1] < x) return n + 2;
        int cur = 1;
        while (cur < sz) {
            cur *= 2;
            if (val[cur] < x) ++cur;
        }
        return cur - sz;
    }
    int reachr(int x) {
        if (val[1] < x) return -1 - 2;
        int cur = 1;
        while (cur < sz) {
            cur *= 2;
            if (val[cur + 1] >= x) ++cur;
        }
        return cur - sz;
    }
};
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int H, W, Q;
    cin >> H >> W >> Q;
    vector<int> X(Q), Y(Q), L(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> Y[i] >> X[i] >> L[i]; --X[i], --Y[i];
    }
    vector<int> sz(4);
    vector<unordered_map<int, int> > dat(4);
    vector<segmenttree> seg(4);
    for (int i = 0; i < 4; ++i) {
        sz[i] = (i % 2 == 0 ? H : W);
        seg[i] = segmenttree(sz[i]);
    }
    for (int i = 0; i < Q; ++i) {
        int dir = -1, pos = -1;
        if (Y[i] == -1) {
            dir = 0, pos = X[i];
        }
        if (X[i] == H) {
            dir = 1, pos = Y[i];
        }
        if (Y[i] == W) {
            dir = 2, pos = H - X[i] - 1;
        }
        if (X[i] == -1) {
            dir = 3, pos = W - Y[i] - 1;
        }
        int val1 = seg[(dir + 1) % 4].reachl(sz[dir] - pos) + 1;
        int val2 = sz[(dir + 1) % 4] - dat[(dir + 2) % 4][sz[dir] - pos - 1] + 1;
        int val3 = sz[(dir + 1) % 4] - seg[(dir + 3) % 4].reachr(pos + 1);
        int mn = min({ val1, val2, val3 });
        int plen = dat[dir][pos] + L[i];
        if (plen < mn) {
            dat[dir][pos] = plen;
            seg[dir].update(pos, plen);
        }
        else {
            dat[dir][pos] = 0;
            seg[dir].update(pos, 0);
            if (mn == val2) {
                dat[(dir + 2) % 4][sz[dir] - pos - 1] = 0;
                seg[(dir + 2) % 4].update(sz[dir] - pos - 1, 0);
            }
            else if (mn == val1) {
                dat[(dir + 1) % 4][val1 - 1] = 0;
                seg[(dir + 1) % 4].update(val1 - 1, 0);
            }
            else {
                dat[(dir + 3) % 4][sz[(dir + 1) % 4] - val3] = 0;
                seg[(dir + 3) % 4].update(sz[(dir + 1) % 4] - val3, 0);
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i < 4; ++i) {
        for (pair<int, int> j : dat[i]) {
            ans += j.second;
        }
    }
    cout << ans << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0