結果

問題 No.961 Vibrant Fillumination
ユーザー kyort0nkyort0n
提出日時 2019-12-24 01:09:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 5,006 bytes
コンパイル時間 2,184 ms
コンパイル使用メモリ 190,240 KB
実行使用メモリ 45,568 KB
最終ジャッジ日時 2024-09-19 05:37:22
合計ジャッジ時間 24,375 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
10,752 KB
testcase_01 AC 4 ms
10,624 KB
testcase_02 AC 1,701 ms
44,400 KB
testcase_03 AC 1,707 ms
42,112 KB
testcase_04 AC 1,664 ms
40,320 KB
testcase_05 AC 1,805 ms
41,216 KB
testcase_06 AC 1,712 ms
44,288 KB
testcase_07 AC 1,732 ms
43,648 KB
testcase_08 AC 1,766 ms
44,204 KB
testcase_09 AC 1,742 ms
44,288 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
ll N, H[50050], a[50500], b[50500], c[50500], d[50500], e[50500];
ll Q;
ll p[50500], q[50500];
ll ans[55000];
vector<ll> Push[100020], Remove[100020], Query[100200];

/*
void check(map<int, int> mp) {
    for(auto val : mp) {
        if(val.second == 0) exit(0);
    }
}
*/


struct LazySegmentTree {
private:
    int n;
    vector<map<int, int>> node;
    vector<ll> hash;

public:
    LazySegmentTree(int _sz) {
        int sz = _sz;
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        hash.resize(2*n-1, 0);
    }

    /*
    void check() {
        for(int i = 0; i < 2 * n - 2; i++) {
            cerr << "-----" << i << "-----" << node[i].size() << endl;
            for(auto val : node[i]) {
                cerr << val.first << " " << val.second << endl;
            }
        }
    }
    */
    /*
    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] ^= lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] ^= lazy[k];
                lazy[2*k+2] ^= lazy[k];
            }
            lazy[k] = 0;
        }
    }
    */

    void add(int a, int b, int x, int y, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        //eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            node[k][x] += y;
            if(node[k][x] == y) {
                hash[k] ^= H[x];
            } else if(node[k][x] == 0) {
                hash[k] ^= H[x];
                node[k].erase(x);
            }
            //cerr << l << " " << r << " " << x << " " << y << " " << node[k][x] << endl;
            //lazy[k] ^= x;
            //eval(k, l, r);
        }
        else {
            add(a, b, x, y, 2*k+1, l, (l+r)/2);
            add(a, b, x, y, 2*k+2, (l+r)/2, r);
            //node[k] = node[2*k+1] ^ node[2*k+2];
        }
    }

    ll getxor(int x) {
        x += (n - 1);
        stack<i_i> sta;
        map<int, int> mp;
        ll ans = 0;
        while(x >= 0) {
            sta.push({x, 1});
            if(node[x].size() > mp.size()) {
                sta.top().second *= -1;
                swap(node[x], mp);
                swap(ans, hash[x]);
            }
            for(auto val : node[x]) {
                mp[val.first] += val.second;
                if(mp[val.first] == val.second) {
                    ans ^= H[val.first];
                }
            }
            //check(mp);
            //check(node[x]);
            //node[x] = min(node[2*x+1], node[2*x+2]);
            if(x == 0) break;
            x = (x - 1) / 2;
        }
        ll ret = ans;
        while(!sta.empty()) {
            int y = sta.top().first;
            int x = sta.top().second;
            sta.pop();
            for(auto val : node[y]) {
                mp[val.first] -= val.second;
                if(mp[val.first] == 0) {
                    ans ^= H[val.first];
                    mp.erase(val.first);
                }
            }
            //check(mp);
            //check(node[y]);
            if(x < 0) {
                swap(node[y], mp);
                swap(ans, hash[y]);
            }
        }
        return ret;
    }

/*
    ll getxor(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);

        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        ll vl = getxor(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getxor(a, b, 2*k+2, (l+r)/2, r);
        return vl ^ vr;
    }
*/
};


int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for(int i = 0; i < N; i++) cin >> H[i];
    for(int i = 0; i < N; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i] >> e[i];
        e[i]--;
        Push[a[i]].push_back(i);
        Remove[c[i]].push_back(i);
    }
    cin >> Q;
    for(int i = 0; i < Q; i++) {
        cin >> p[i] >> q[i];
        Query[p[i]].push_back(i);
    }
    LazySegmentTree seg(2 * N + 1);
    for(int h = 0; h <= 2 * N; h++) {
        for(auto index : Push[h]) {
            seg.add(b[index], d[index], e[index], 1);
        }
        for(auto index : Remove[h]) {
            seg.add(b[index], d[index], e[index], -1);
        }
        for(auto index : Query[h]) {
            ans[index] = seg.getxor(q[index]);
        }
        //seg.check();
        /*
        for(int i = 0; i <= 10; i++) {
            cerr << seg.getxor(i) << " ";
        }
        cerr << endl;
        */
    }
    for(int i = 0; i < Q; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}
0