結果

問題 No.961 Vibrant Fillumination
ユーザー kyort0n
提出日時 2019-12-24 01:32:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,449 bytes
コンパイル時間 2,574 ms
コンパイル使用メモリ 202,192 KB
実行使用メモリ 49,572 KB
最終ジャッジ日時 2024-09-19 05:51:55
合計ジャッジ時間 22,721 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

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 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) {
            int tmp = (++node[k][x]);
            if(tmp == 1) {
                hash[k] ^= H[x];
            }
            //cerr << l << " " << r << " " << x << " " << y << " " << node[k][x] << endl;
            //lazy[k] ^= x;
            //eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            //node[k] = node[2*k+1] ^ node[2*k+2];
        }
    }

    void Minus(int a, int b, int x, 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) {
            int tmp = (--node[k][x]);
            if(tmp == 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 {
            Minus(a, b, x, 2*k+1, l, (l+r)/2);
            Minus(a, b, x, 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]) {
                if((++mp[val.first]) == 1) {
                    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]) {
                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]);
        }
        for(auto index : Remove[h]) {
            seg.Minus(b[index], d[index], e[index]);
        }
        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