제출 #633930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633930		fabijan_cikac	Segments (IZhO18_segments)	C++17	75 / 100	5048 ms	5516 KiB

segments

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define pp pair<int, int>
#define ppp pair<int, pp>
#define F first
#define S second
#define pb push_back

const int N = 2 * 1e5 + 100;
const int BK = 450;
const int INF = 2 * 1e9 + 10;

int n, t; int buck = 0;
vector<ppp> a[BK];
vector<ppp> b[BK];
vector<ppp> trash;
vector<ppp> trash2;
pp xy[N]; vector<int> L[BK][2];
vector<int> R[BK][2];

vector<ppp> st;
void move_trash(){
    st.clear();
    for (auto i: trash) st.pb(i);
    trash.clear();
    for (int i = 0; i < BK; ++i){
        if (a[i].empty()) continue;
        for (auto j: a[i]) st.pb(j);
        a[i].clear(); L[i][0].clear(); R[i][0].clear();
    }
    sort(st.begin(), st.end());
    for (int i = 0; i < st.size(); ++i){
        a[i / buck].pb(st[i]);
        L[i / buck][0].pb(st[i].S.F);
        R[i / buck][0].pb(st[i].S.S);
    }
    for (int i = 0; i < BK; ++i){
        sort(L[i][0].begin(), L[i][0].end());
        sort(R[i][0].begin(), R[i][0].end());
    }
}

void move_trash2(){
    st.clear();
    for (auto i: trash2) st.pb(i);
    trash2.clear();
    for (int i = 0; i < BK; ++i){
        if (b[i].empty()) continue;
        for (auto j: b[i]) st.pb(j);
        b[i].clear(); L[i][1].clear(); R[i][1].clear();
    }
    sort(st.begin(), st.end());
    for (int i = 0; i < st.size(); ++i){
        b[i / buck].pb(st[i]);
        L[i / buck][1].pb(st[i].S.F);
        R[i / buck][1].pb(st[i].S.S);
    }
    for (int i = 0; i < BK; ++i){
        sort(L[i][1].begin(), L[i][1].end());
        sort(R[i][1].begin(), R[i][1].end());
    }
}

int bins_a(int l, int r, int k){
    if (l == r) return l;
    int mid = (l + r + 1) / 2;
    if (a[mid].empty() || a[mid].back().F >= k) return bins_a(l, mid - 1, k);
    return bins_a(mid, r, k);
}

int bins_b(int l, int r, int k){
    if (l == r) return l;
    int mid = (l + r + 1) / 2;
    if (b[mid].empty() || b[mid].back().F >= k) return bins_b(l, mid - 1, k);
    return bins_b(mid, r, k);
}

int bins_R(int x, int fl, int val, int l, int r){
    if (l == r) return l;
    int mid = (l + r + 1) / 2;
    if (R[x][fl][mid] < val)
        return bins_R(x, fl, val, mid, r);
    return bins_R(x, fl, val, l, mid - 1);
}

int bins_L(int x, int fl, int val, int l, int r){
    if (l == r) return l;
    int mid = (l + r - 1) / 2;
    if (L[x][fl][mid] > val)
        return bins_L(x, fl, val, l, mid);
    return bins_L(x, fl, val, mid + 1, r);
}

//if intersect
bool inct(int l1, int r1, int l2, int r2, int k){
    if (l1 > l2){
        swap(l1, l2); swap(r1, r2);
    }
    r1 = min(r1, r2);
    if ((r1 - l2 + 1) >= k)
        return 1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> t;
    buck = n / BK + 1;
    int lastans = 0; int cnt = 1;
    int id = 1;
    for (int i = 0; i < n; ++i){
        int u; cin >> u;
        if (cnt % buck == 0){
            move_trash();
            move_trash2();
        }
        if (u == 1){
            int l, r; cin >> l >> r;
            l = (l ^ (t * lastans));
            r = (r ^ (t * lastans));
            if (l > r) swap(l, r);
            trash.pb({r - l + 1, {l, r}});
            sort(trash.begin(), trash.end());
            xy[id] = {l, r}; ++cnt; ++id;
        }
        else if (u == 2){
            int id; cin >> id;
            trash2.pb({xy[id].S - xy[id].F + 1, xy[id]});
            sort(trash2.begin(), trash2.end()); ++cnt;
        }
        else{
            int l, r, k; cin >> l >> r >> k;
            l = (l ^ (t * lastans));
            r = (r ^ (t * lastans));
            if (l > r) swap(l, r);
            if (k > r - l + 1){
                cout << 0 << '\n'; lastans = 0; continue;
            }
            int ans = 0;
            for (auto x: trash){
                if (inct(l, r, x.S.F, x.S.S, k)) ++ans;
            }
            for (auto x: trash2){
                if (inct(l, r, x.S.F, x.S.S, k)) --ans;
            }
            int pos1 = bins_a(0, BK - 1, k) + 1;
            if (a[0].empty() || a[0].back().F >= k) pos1 = 0;
            for (auto x: a[pos1]){
                if (inct(l, r, x.S.F, x.S.S, k)) ++ans;
            }
            int pos2 = bins_b(0, BK - 1, k) + 1;
            if (b[0].empty() || b[0].back().F >= k) pos2 = 0;
            for (auto x: b[pos2]){
                if (inct(l, r, x.S.F, x.S.S, k)) --ans;
            }
            for (int i = pos1 + 1; i < BK; ++i){
                if (a[i].empty()) break;
                int num = a[i].size();
                if (L[i][0].back() > r - k + 1)
                    num -= (L[i][0].size() - bins_L(i, 0, r - k + 1, 0, L[i][0].size() - 1));
                if (R[i][0][0] < l + k - 1)
                    num -= (bins_R(i, 0, l + k - 1, 0, R[i][0].size() - 1) + 1);
                ans += num;
            }
            for (int i = pos2 + 1; i < BK; ++i){
                if (b[i].empty()) break;
                int num = b[i].size();
                if (L[i][1].back() > r - k + 1)
                    num -= (L[i][1].size() - bins_L(i, 1, r - k + 1, 0, L[i][1].size() - 1));
                if (R[i][1][0] < l + k - 1)
                    num -= (bins_R(i, 1, l + k - 1, 0, R[i][1].size() - 1) + 1);
                ans -= num;
            }
            lastans = ans; cout << ans << '\n';
        }
    }

    return 0;
}

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

segments.cpp: In function 'void move_trash()':
segments.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < st.size(); ++i){
      |                     ~~^~~~~~~~~~~
segments.cpp: In function 'void move_trash2()':
segments.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < st.size(); ++i){
      |                     ~~^~~~~~~~~~~

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