Submission #879022

#	Time	Username	Problem	Language	Result	Execution time	Memory
879022		dimashhh	Segments (IZhO18_segments)	C++17	7 / 100	865 ms	23132 KiB

segments

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, MOD = 998244353;

int q,t,it = 1,lst = 0,b = 10000;
pair<int,int> id[N];
multiset<pair<int,int>> st;
vector<pair<pair<int,int>,int>> f;
vector<int> gr[N],gl[N],br[500],bl[500];
void rebuild(){
    int it = 0;
    vector<pair<int,int>> L,R;
    for(auto [l,r]:st){
        L.push_back({r - l + 1,l});
        R.push_back({r - l + 1,r});
        if(r - l + 1 < 0){
            while(true){

            }
        }
        gr[r - l + 1].clear();
        gl[r - l + 1].clear();
        // br[(r - l + 1) / b].clear();
        // bl[(r - l + 1) / b].clear();
    }
    
    sort(L.begin(),L.end());
    sort(R.begin(),R.end());
    for(int i = 0;i < (int)L.size();i++){
        gl[L[i].first].push_back(L[i].second);
        gr[R[i].first].push_back(R[i].second);
        // bl[L[i].first / b].push_back(L[i].second);
        // br[R[i].first / b].push_back(R[i].second);
    }
}
int more(int val,vector<int> &x){
    int it = upper_bound(x.begin(),x.end(),val) - x.begin();
    return (x.size() - it);
}
int LE(int val,vector<int> &x){
    int it = lower_bound(x.begin(),x.end(),val) - x.begin();
    return it;
}
int getr(int l,int val){
    int ret = 0;
    for(int j = l;j < N;j++){
        for(auto i:gr[j]){
            if(i < val) ret++;
        }
        // ret += LE(val,gr[j]);
    }
    return ret;
}
int getl(int l,int val){
    int ret = 0;
    for(int j = l;j < N;j++){
        for(int i:gl[j]){
            if(i >val) ret++;
        }
        // ret += more(val,gl[j]);
    }
    return ret;
}
void test(){
    cin >> q >> t;
    int sz;
    for(int i = 1;i <= q;i++){
        int tp;
        cin >> tp;
        if(i % b == 1){
            rebuild();
            f.clear();
            sz = st.size();
        }
        if(tp == 1){
            int l,r;
            cin >> l >> r;
            l = (l ^ (t * lst));
            r = (r ^ (t * lst));
            if(l > r) swap(l,r);
            id[it++] = {l,r};
            st.insert({l,r});
            f.push_back({{l,r},1});
        }else if(tp == 2){
            int j;
            cin >> j;
            st.erase(st.find(id[j]));
            f.push_back({{id[j].first,id[j].second},-1});
        }else{
            int l,r,k;
            cin >> l >> r >> k;
            l = (l ^ (t * lst));
            r = (r ^ (t * lst));
            if(l > r) swap(l,r);
            if(r - l + 1 < k){
                lst = 0;
                cout << lst << '\n';
                continue;
            }
            int res = sz - getr(k,l + k - 1) - getl(k,r - k + 1);
            for(auto [x,y]:f){
                int L = x.first,R = x.second;
                if(R - L + 1 < k) continue;
                if(R < l + k - 1) continue;
                if(L > r - k + 1) continue;
                res += y;
            }
            cout << res << '\n';
            lst = res;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        test();
    }
}

Compilation message (stderr)

segments.cpp: In function 'void rebuild()':
segments.cpp:12:9: warning: unused variable 'it' [-Wunused-variable]
   12 |     int it = 0;
      |         ^~
segments.cpp: In function 'void test()':
segments.cpp:101:26: warning: 'sz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |             int res = sz - getr(k,l + k - 1) - getl(k,r - k + 1);
      |                       ~~~^~~~~~~~~~~~~~~~~~~

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