Submission #879035

#	Time	Username	Problem	Language	Result	Execution time	Memory
879035		dimashhh	Segments (IZhO18_segments)	C++17	100 / 100	4389 ms	25300 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 = 1500;
pair<int,int> id[N];
multiset<pair<int,int>> st;
vector<pair<pair<int,int>,int>> f;
vector<pair<int,int>> br[500],bl[500];
int mx[500],mn[500];
void rebuild(){
    int it = 0;
    vector<pair<int,int>> L,R;
    for(int i = 0;i <200;i++){
        br[i].clear();
        bl[i].clear();
        mx[i] = -1;
        mn[i] = 2e9;
    }
    for(auto [l,r]:st){
        L.push_back({r - l + 1,l});
        R.push_back({r - l + 1,r});
    }
    
    sort(L.begin(),L.end());
    sort(R.begin(),R.end());
    for(int i = 0;i < (int)L.size();i++){
        bl[i / b].push_back({L[i].second,L[i].first});
        br[i / b].push_back({R[i].second,R[i].first});
        mn[i / b] = min(mn[i / b],L[i].first);
        mx[i / b] = max(mx[i / b],L[i].first);
    }
    for(int i = 0;i < 200;i++){
        sort(bl[i].begin(),bl[i].end());
        sort(br[i].begin(),br[i].end());
    }
}
int more(int val,vector<pair<int,int>> &x){
    int it = lower_bound(x.begin(),x.end(),make_pair(val,2000000000)) - x.begin();
    return (x.size() - it);
}
int LE(int val,vector<pair<int,int>> &x){
    int it = lower_bound(x.begin(),x.end(),make_pair(val,0)) - x.begin();
    return it;
}
int getsz(int l){
    int ret = 0;
    for(int j = 0;j < 200;j++){
        if(mx[j] < l) continue;
        if(mn[j] >= l){
            ret += br[j].size();
            continue;
        }
        for(auto [i,k]:br[j]){
            ret += (k >= l);
        }
    }
    return ret;
}
int getr(int l,int val){
    int ret = 0;
    for(int j = 0;j < 200;j++){
        if(mx[j] < l) continue;
        if(mn[j] >= l){
            ret += LE(val,br[j]);
            continue;
        }
        for(auto [i,k]:br[j]){
            if(k >= l && i < val) ret++;
        }
    }
    return ret;
}
int getl(int l,int val){
    int ret = 0;
    for(int j = 0;j < 200;j++){
        if(mx[j] < l) continue;
        if(mn[j] >= l){
            ret += more(val,bl[j]);
            continue;
        }
        for(auto [i,k]:bl[j]){
            if(i > val && k >= l) ret++;
        }
    }
    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 = getsz(k) - 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:13:9: warning: unused variable 'it' [-Wunused-variable]
   13 |     int it = 0;
      |         ^~
segments.cpp: In function 'void test()':
segments.cpp:91:9: warning: variable 'sz' set but not used [-Wunused-but-set-variable]
   91 |     int sz;
      |         ^~

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