Submission #878424

#	Time	Username	Problem	Language	Result	Execution time	Memory
878424		dimashhh	Segments (IZhO18_segments)	C++17	7 / 100	5057 ms	8160 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;
pair<int,int> id[N];
multiset<pair<int,int>> st;
vector<pair<pair<int,int>,int>> f;
void test(){
    cin >> q >> t;
    for(int i = 1;i <= q;i++){
        int tp;
        cin >> tp;
        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 = 0;
            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();
    }
}

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