제출 #682617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682617		phoenix	Segments (IZhO18_segments)	C++17	15 / 100	709 ms	6172 KiB

segments

#include<bits/stdc++.h>

using namespace std;
const int N = (1 << 17);
const int B = 317;
struct tree {
    vector<int> st[N / B + 10];
    vector<int> a;
    int sz = 0;
    void init(vector<int> &a) {
        this->a = a;
        sz = (int)a.size();
        build();
    }
    void build() {
        for(int i = 0; i < sz; i++) {
            st[i / B].push_back(a[i]);
        }
        for(int i = 0; i <= (sz - 1) / B; i++) 
            sort(st[i].begin(), st[i].end());
    }
    int get(int ql, int qr, int x) {
        int ans = 0;
        while(ql <= qr) {
            bool f = (ql % B == 0 && ql + B - 1 <= qr);
            if(f) {
                int lb = -1, rb = (int)st[ql / B].size();
                while(rb - lb > 1) {
                    int m = (lb + rb) / 2;
                    if(st[ql / B][m] < x) lb = m;
                    else rb = m;
                }
                ans += lb + 1;
                ql += B;
            } else {
                ans += (a[ql] < x);
                ql++;
            }
        }
        return ans;
    }
};
vector<pair<int, int>> v;
// left bounds, right bounds
vector<int> ll, rr;
tree t1, t2;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    int n, t;
    cin >> n >> t;
    int lastans = 0;
    bool isBuilt = 0;
    for(int i = 1; i <= n; i++) {
        int type;
        cin >> type;
        if(type == 1) {
            int l, r;
            cin >> l >> r;
            l = (l ^ (t * lastans));
            r = (r ^ (t * lastans));
            if(l > r) swap(l, r);
            v.push_back({l, r});
        } else {
            if(!isBuilt) {
                sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b){return a.second - a.first < b.second - b.first;});
                for(int i = 0; i < (int)v.size(); i++) {
                    ll.push_back(v[i].first);
                    rr.push_back(v[i].second);
                }
                t1.init(ll);
                t2.init(rr);
                isBuilt = 1;
            }
            int l, r, k;
            cin >> l >> r >> k;
            l = (l ^ (t * lastans));
            r = (r ^ (t * lastans));
            lastans = 0;
            if(l > r) swap(l, r);
            if(r - l + 1 < k) {
                cout << 0 << '\n';
                continue;
            }

            int lb = -1, rb = (int)v.size();
            while(rb - lb > 1) {
                int m = (lb + rb) / 2;
                if(v[m].second - v[m].first + 1 >= k) rb = m;
                else lb = m;
            }
            lastans = t1.get(rb, (int)v.size() - 1, r - k + 2) - t2.get(rb, (int)v.size() - 1, l + k - 1);
            cout << lastans << '\n';
        }
    }
}

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