Submission #201158

#	Time	Username	Problem	Language	Result	Execution time	Memory
201158		darkkcyan	Segments (IZhO18_segments)	C++17	0 / 100	5075 ms	8872 KiB

segments

// vim: foldmethod=marker
// Sun Feb  9 11:53:54 MSK 2020: START coding
// Sun Feb  9 12:04:53 MSK 2020: PAUSE
// Sun Feb  9 12:10:50 MSK 2020: CONTINUE
// Sun Feb  9 13:05:32 MSK 2020
#include <bits/stdc++.h>
using namespace std;

#define llong long long 
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define rand __rand
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
template<class T = int> T rand(T range = numeric_limits<T>::max()) { return (T)(rng() % range); }

/*{{{*/
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL_DEBUG   
int debug = 1;
#define DB(...) stringstream CONCAT(ss, __LINE__); CONCAT(ss, __LINE__) << __VA_ARGS__; debug_block CONCAT(dbbl, __LINE__)(CONCAT(ss, __LINE__).str())
#else
int debug = 0;
#define DB(...)
#endif
int __db_level = 0;
#define clog if (debug) cerr << string(__db_level * 2, ' ')
struct debug_block {
    string name;
    debug_block(const string& name_): name(name_) { clog << "{ " << name << endl; ++__db_level; }
    ~debug_block() { --__db_level; clog << "} " << name << endl; }
};
#define deb(...) "[" << #__VA_ARGS__ << "] = [" << __VA_ARGS__ << "]"
#define debln(...)  clog << "[" << #__VA_ARGS__ << "] = [" << __VA_ARGS__ << "]" << endl
#define _ << ", " <<
template<class U, class V>
ostream& operator<<(ostream& out, const pair<U, V>& p) { return out << "(" << p.first _ p.second << ")"; }
template<class A, class B>
ostream& operator<<(ostream& out, const tuple<A, B>& t) { return out << "(" << get<0>(t) _ get<1>(t) << ")"; }
template<class A, class B, class C>
ostream& operator<<(ostream& out, const tuple<A, B, C>& t) { return out << "(" << get<0>(t) _ get<1>(t) _ get<2>(t) << ")"; }
template<class T> ostream& operator<<(ostream& out, const vector<T>& container) { 
    out << "{";
    if (len(container)) out << container[0];
    rep1(i, len(container) - 1) out _ container[i];
    return out << "}";
}
template<class x> vector<typename x::value_type> $v(const x& a) { return vector<typename x::value_type>(a.begin(), a.end()); }
#define ptrtype(x) typename iterator_traits<x>::value_type
template<class u> vector<ptrtype(u)> $v(u a, u b) { return vector<ptrtype(u)>(a, b); }
/*}}}*/
// ACTUAL SOLUTION BELOW ////////////////////////////////////////////////////////////

#ifdef LOCAL
const int bucket_size = 3;  // for testing
#else
const int bucket_size = 450;
#endif
const int maxn = 200'100;
struct segment {
    int l, r;
    bool removed = false;

    segment() = default;
    segment(int l_, int r_) : l(l_), r(r_) {}
    inline int length() const { return r - l + 1; }

    friend int cnt_intersect(const segment& lhs, const segment& rhs) {
        if (lhs.l > rhs.r or rhs.l > lhs.r) return 0;
        return min(lhs.r, rhs.r) - max(lhs.l, rhs.l) + 1;
    }

    static bool cmp_by_length(const segment& u, const segment& v) { return u.length() < v.length(); }
    static bool cmp_by_left(const segment& u, const segment& v) { return u.l < v.l; }
    static bool cmp_by_right(const segment& u, const segment& v) { return u.r < v.r; }
};

ostream& operator<<(ostream& out, const segment& seg) {
    return out << "segment(" <<
        "l = " << seg.l _
        "r = " << seg.r _
        "removed = " << seg.removed <<
        ")";
}

template<class T>
function<bool(T*, T*)> cmp_ptr(const function<bool(const T& u, const T& v)>& cmp_ref) {
    return [&](T* u, T* v) -> bool { return cmp_ref(*u, *v); };
}


struct bucket {
    int min_length, max_length;
    vector<segment*> left, right;
    bucket() {}

    template<class iter>
    void assign(iter beg, iter end) {
        left.clear();
        right.clear();
        int dst = (int)distance(beg, end);
        left.reserve(dst);
        right.reserve(dst);
        min_length = (*min_element(beg, end, cmp_ptr<segment>(segment::cmp_by_length)))->length();
        max_length = (*max_element(beg, end, cmp_ptr<segment>(segment::cmp_by_length)))->length();
        for (; beg < end; ++beg) {
            left.push_back(*beg);
            right.push_back(*beg);
        }
    
        sort(left.begin(), left.end(), cmp_ptr<segment>(segment::cmp_by_left));
        sort(right.begin(), right.end(), cmp_ptr<segment>(segment::cmp_by_right));
    }

    int query(segment const& qr, int k) {
        if (min_length > k) return 0;
        if (max_length < k) return len(left);
        if (min_length <= k and k <= max_length) {
            int ans = 0;
            for (auto& seg: left) {
                if (seg->length() < k) ++ ans;
                else if (segment(seg->l, qr.r).length() < k) ++ans;
                else if (segment(qr.l, seg->r).length() < k) ++ans;
            }
            return ans;
        }

        segment upper_left(qr.r - k + 1, qr.r), lower_right(qr.l, qr.l + k - 1);

        return (int)(
            (left.end() -  upper_bound(left.begin(), left.end(), &upper_left, cmp_ptr<segment>(segment::cmp_by_left))) + 
            (lower_bound(right.begin(), right.end(), &lower_right, cmp_ptr<segment>(segment::cmp_by_right)) - right.begin())
        );
    }
};

set<int> inactive_id;
segment all_segment[maxn];

vector<segment*> added_segments;
int n_bucket = 0;
bucket buckets[maxn / bucket_size + 10];

vector<segment*> current_added;
vector<segment> current_removed;

void rebuild() {
    added_segments.insert(added_segments.begin(), current_added.begin(), current_added.end());
    added_segments.resize(
            remove_if(added_segments.begin(), added_segments.end(), [](segment* u) { return u->removed; }) -
            added_segments.begin()
    );
    current_added.clear();
    current_removed.clear();
    sort(added_segments.begin(), added_segments.end(), cmp_ptr<segment>(segment::cmp_by_length));
    n_bucket = 0;
    for (int i = 0; i < len(added_segments); i += bucket_size, ++n_bucket)
        buckets[n_bucket].assign(added_segments.begin() + i, added_segments.begin() + min(i + bucket_size, len(added_segments)));
}

void do_add(segment new_seg) { 
    int id = *inactive_id.begin();
    inactive_id.erase(inactive_id.begin());
    all_segment[id] = new_seg;
    current_added.push_back(all_segment + id);
}

void do_remove(int id) {
    all_segment[id].removed = true;
    current_removed.push_back(all_segment[id]);
    inactive_id.insert(id);
}

int do_query(segment querying_seg, int k) {
    if (querying_seg.length() < k) return 0;
    int ans = len(added_segments);
    rep(i, n_bucket) ans -= buckets[i].query(querying_seg, k);

    for (auto& seg: current_added) 
        if (cnt_intersect(*seg, querying_seg) >= k) ++ans;
    for (auto& seg: current_removed) 
        if (cnt_intersect(seg, querying_seg) >= k) --ans;
    return ans;
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, t; cin >> n >> t;
    int last_ans = 0;
    rep1(i, n) inactive_id.insert(i);
    rep1(nquery, n) {
        DB(deb(nquery));
        int qr_type; cin >> qr_type;
        segment new_seg; int num;
        if (qr_type == 1 or qr_type == 3) {
            int l, r; cin >> l >> r;
            l ^= t * last_ans;
            r ^= t * last_ans;
            if (l > r) swap(l, r);
            new_seg = segment(l, r);
        }
        if (qr_type == 2 or qr_type == 3) cin >> num;
        debln(qr_type _ new_seg _ num);

        if (qr_type == 1) do_add(new_seg);
        else if (qr_type == 2) do_remove(num);
        else if (qr_type == 3) {
            last_ans = do_query(new_seg, num);
            cout << last_ans  << '\n';
        }
        else assert(false);

        if (nquery % n == 0) rebuild();
    }


    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25