제출 #443240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443240		nickyrio	Segments (IZhO18_segments)	C++17	100 / 100	2327 ms	8828 KiB

segments

#include <bits/stdc++.h>

using namespace std;

int lastans = 0, t;
int decode(int x) { return x ^ (t * lastans); }

const int NUM_BLOCK = 500;
const int BLOCK_SIZE = 1500;

class Solver {
    
    vector< pair<int, int> > pending, all;
    vector< int > left_base[NUM_BLOCK], right_base[NUM_BLOCK];

    int intersect(pair<int, int> a, pair<int, int> b, int k) {
        int l = max(a.first, b.first), r = min(b.second, a.second);
        return r - l + 1 >= k;
    }

    void rebuild() {
        // cerr << "Rebuilding...\n";
        vector< pair<int, int> > temp(all.size() + pending.size());
        merge(pending.begin(), pending.end(), all.begin(), all.end(), temp.begin());
        pending.clear();
        swap(temp, all);

        sort(all.begin(), all.end(), [&](const pair<int, int>&a, const pair<int, int>&b) {
                return a.second - a.first < b.second - b.first;
        });
        for (int l = 0; l < all.size(); l += BLOCK_SIZE) {
            left_base[l / BLOCK_SIZE].clear();
            right_base[l / BLOCK_SIZE].clear();
        }
        for (int l = 0; l < all.size(); l += BLOCK_SIZE) {
            int id = l / BLOCK_SIZE;
            int r = min(l + BLOCK_SIZE, (int)all.size());
            for (int i = l; i < r; ++i) {
                // cerr << "Add " << all[i].first << ' ' << all[i].second << " to block " << id << '\n';
                left_base[id].push_back(all[i].first);
                right_base[id].push_back(all[i].second);
            }
        }
      for (int id = 0; id * BLOCK_SIZE < all.size(); ++id) {
            sort(left_base[id].begin(), left_base[id].end());
            sort(right_base[id].begin(), right_base[id].end());
        }
    }
public:
    void add(int l, int r) {
        // cerr << "Add segment [" << l << ',' << r << "]\n";
        pending.emplace_back(l, r);
        if (pending.size() >= BLOCK_SIZE) rebuild();
    }

    int query(pair<int, int> q_seg, int k) {
        // cerr << "Query segment [" << q_seg.first << ',' << q_seg.second << "] with k = " << k << '\n';
        if (q_seg.second - q_seg.first + 1 < k) return 0;
        int ans = 0;
        for (auto seg : pending) ans += intersect(q_seg, seg, k);
        for (int l = 0; l < all.size(); l += BLOCK_SIZE) {
            int id = l / BLOCK_SIZE, r = min(l + BLOCK_SIZE, (int) all.size()) - 1;
            // cerr << "Query block " << id <<' ' << all[l].first << ' ' << all[l].second << '\n';
            if (all[l].second - all[l].first + 1 >= k) {
                int cur = 0;
                ans += r - l + 1;
                // [l, l + k - 1] -> remove R < l + k - 1
                ans -= lower_bound(right_base[id].begin(), right_base[id].end(), q_seg.first + k - 1) - right_base[id].begin();
                // [r - k + 1, r] -> remove L > r - k + 1
                ans -= left_base[id].end() - upper_bound(left_base[id].begin(), left_base[id].end(), q_seg.second - k + 1);
            } else {
                if (all[r].second - all[r].first + 1 >= k) {
                    // Trigger only one block
                    for (int i = l; i <= r; ++i) ans += intersect(q_seg, all[i], k);
                }
            }
        }
        return ans;
    }
}addSolver, delSolver;
vector< pair<int, int> > history;

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin >> n >> t;
    for (int i = 0; i < n; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            l = decode(l), r = decode(r);
            if (l > r) swap(l, r);
            history.emplace_back(l, r);
            addSolver.add(l, r);
        } else if (type == 2) {
            int id; cin >> id;
            auto [l, r] = history[id - 1];
            delSolver.add(l, r);
        } else {
            int l, r, k; cin >> l >> r >> k;
            l = decode(l), r = decode(r);
            if (l > r) swap(l, r);
            lastans = addSolver.query({l, r}, k) - delSolver.query({l, r}, k);
            cout << lastans << '\n';
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

segments.cpp: In member function 'void Solver::rebuild()':
segments.cpp:31:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int l = 0; l < all.size(); l += BLOCK_SIZE) {
      |                         ~~^~~~~~~~~~~~
segments.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int l = 0; l < all.size(); l += BLOCK_SIZE) {
      |                         ~~^~~~~~~~~~~~
segments.cpp:44:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       for (int id = 0; id * BLOCK_SIZE < all.size(); ++id) {
      |                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~~
segments.cpp: In member function 'int Solver::query(std::pair<int, int>, int)':
segments.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int l = 0; l < all.size(); l += BLOCK_SIZE) {
      |                         ~~^~~~~~~~~~~~
segments.cpp:65:21: warning: unused variable 'cur' [-Wunused-variable]
   65 |                 int cur = 0;
      |                     ^~~

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