Submission #201216

#	Time	Username	Problem	Language	Result	Execution time	Memory
201216		darkkcyan	Segments (IZhO18_segments)	C++17	15 / 100	3151 ms	9320 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 {
    llong l, r;

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

    friend llong 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;
    }

    bool is_removed() { return l > r; }

    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 << 
        ")";
}

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 {
    llong 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, segment::cmp_by_length)->length();
        max_length = max_element(beg, end, segment::cmp_by_length)->length();
        for (; beg < end; ++beg) {
            left.push_back(*beg);
            right.push_back(*beg);
        }
    
        sort(left.begin(), left.end(), segment::cmp_by_left);
        sort(right.begin(), right.end(), segment::cmp_by_right);
    }

    int query(segment const& qr, llong k) {
        if (k == 0) return len(left);
        if (max_length < k) return 0;
        if (min_length <= k and k <= max_length) {
            int ans = len(left);
            for (auto& seg: left) {
                if (cnt_intersect(seg, qr) < k) -- ans;
            }
            return ans;
        }

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

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

int max_unassigned = 1;
segment all_segments[maxn];
priority_queue<int, vector<int>, greater<int>> inactive_id;

int n_bucket = 0;
bucket buckets[maxn / bucket_size + 10];

vector<segment> current_removed, current_added;

void rebuild() {
    current_removed.clear();
    current_added.clear();

    vector<segment> avaliable_seg;
    copy_if(all_segments + 1, all_segments + max_unassigned, back_inserter(avaliable_seg), not_fn(&segment::is_removed));

    sort(avaliable_seg.begin(), avaliable_seg.end(), segment::cmp_by_length);

    n_bucket = 0;
    for (int i = 0; i < len(avaliable_seg); i += bucket_size)
        buckets[n_bucket++].assign(avaliable_seg.begin() + i, avaliable_seg.begin() + min(i + bucket_size, len(avaliable_seg)));
}

void do_add(segment new_seg) { 
    int id = inactive_id.top();
    inactive_id.pop();
    all_segments[id] = new_seg;
    max_unassigned = max(max_unassigned, inactive_id.top());
    current_added.push_back(new_seg);
}

void do_remove(int id) {
    current_removed.push_back(all_segments[id]);
    all_segments[id].l = all_segments[id].r + 1;
    inactive_id.push(id);
}

int do_query(segment querying_seg, llong k) {
    if (querying_seg.length() < k) return 0;
    int ans = 0;
    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;
}

struct stdio_interactor {
    int n, t;
    int last_ans = 0;
    stdio_interactor() { cin >> n >> t; }

    inline tuple<int, segment, llong> get_query() {
        int qr_type;
        segment new_seg; 
        llong num;
        cin >> qr_type;
        if (qr_type == 1 or qr_type == 3) {
            llong 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;
        return {qr_type, new_seg, num};
    }

    inline void answer(int cur_ans) {
        cout << cur_ans << '\n';
        last_ans = cur_ans;
    }
};

struct test_interactor {
    int n = 3;
    ofstream inp;
    map<int, segment> having_segments;
    int current_ans = -1;

    test_interactor(): inp("test.inp") {
        inp << n << ' ' << 0 << endl;
    }

    ~test_interactor() {
        if (current_ans != -1) {
            clog << "not answering the last query" << endl;
        }
    }

    segment rand_seg() {
        auto l = rand(2'000'000'000L), r = rand(2'000'000'000L);
        if (l > r) swap(l, r);
        return segment(l, r);
    }

    tuple<int, segment, llong> get_query() {
        if (current_ans != -1) {
            clog << "Not answering the previous query" << endl;
            exit(0);
        }

        int qr_type;
        do {
            qr_type = rand(3) + 1;
        } while (qr_type == 2 and !having_segments.size());

        inp << qr_type << ' ';
        segment seg; llong num;
        if (qr_type == 1) {
            seg = rand_seg();
            int cur_id = 1;
            while (having_segments.count(cur_id)) ++cur_id;
            having_segments[cur_id] = seg;
            inp << seg.l << ' ' << seg.r << endl;
        } else if (qr_type == 2) {
            int rem_pos = (int)rand(having_segments.size());
            auto rem_it = next(having_segments.begin(), rem_pos);
            num = rem_it->first;
            inp << num << endl;
            having_segments.erase(rem_it);
        } else {
            seg = rand_seg();
            num = rand(2'000'000'000L);
            current_ans = 0;
            for (auto [id, hseg]: having_segments) {
                current_ans += cnt_intersect(hseg, seg) >= num;
            }
            inp << seg.l << ' ' << seg.r << ' ' << num << endl;
        }
        return {qr_type, seg, num};
    }

    inline void answer(int ans) {
        if (current_ans == -1) {
            clog << "The query does not need to be asnwer" << endl;
            exit(0);
        }
        if (current_ans != ans) {
            clog << "Different answer: " << endl;
            debln(current_ans);
            debln(ans);
            exit(0);
        }
        current_ans = -1;
    }
};

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    stdio_interactor interactor;         
    // test_interactor interactor;         

    rep1(i, interactor.n) inactive_id.push(i);

    rep1(nquery, interactor.n) {
        auto [qr_type, new_seg, num] = interactor.get_query();
        if (qr_type == 1) do_add(new_seg);
        else if (qr_type == 2) do_remove((int)num);
        else if (qr_type == 3) interactor.answer(do_query(new_seg, num));
        else assert(false);

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

    return 0;
}

Compilation message (stderr)

segments.cpp: In member function 'std::tuple<int, segment, long long int> test_interactor::get_query()':
segments.cpp:263:32: warning: unused variable 'id' [-Wunused-variable]
             for (auto [id, hseg]: having_segments) {
                                ^

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