Submission #468913

#	Time	Username	Problem	Language	Result	Execution time	Memory
468913		JovanB	Segments (IZhO18_segments)	C++17	100 / 100	2263 ms	36840 KiB

segments

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 200000;
const int K = 400;
const int INF = 2000000005;

int L[N+5], R[N+5];
int mxl[N+5];
int mnl[N+5];
int gde[N+5];

vector <tuple <ll, int, int>> rs[N+5];
vector <tuple <ll, int, int>> sz[N+5];
vector <tuple <ll, int, int>> vec[N+5];

int n;

int query1(int r, ll val){
    int res = 0;
    for(int i=1; i<=n/K+5; i++){
        if(rs[i].empty() || mnl[i] > r) continue;
        if(mxl[i] <= r){
            auto c = rs[i].end() - lower_bound(rs[i].begin(), rs[i].end(), make_tuple(val, 0, 0));
            res += c;
        }
        else{
            for(auto pr : rs[i]) if(get<0>(pr) >= val && get<1>(pr) <= r) res++;
        }
    }
    return res;
}

int query2(int l, int r, ll val){
    if(r < l) return 0;
    int res = 0;
    for(int i=1; i<=n/K+5; i++){
        if(sz[i].empty() || mnl[i] > r || mxl[i] < l) continue;
        if(l <= mnl[i] && mxl[i] <= r){
            auto c = sz[i].end() - lower_bound(sz[i].begin(), sz[i].end(), make_tuple(val, 0, 0));
            res += c;
        }
        else{
            for(auto pr : sz[i]) if(l <= get<1>(pr) && get<1>(pr) <= r && get<0>(pr) >= val) res++;
        }
    }
    return res;
}

void Rebuild(){
    vector <int> vc;
    for(int i=1; i<=n/K+5; i++){
        for(auto c : vec[i]) vc.push_back(get<2>(c));
        sz[i].clear();
        rs[i].clear();
        vec[i].clear();
        mnl[i] = INF;
        mxl[i] = 0;
    }
    int tjm = 1;
    for(auto i : vc){
        if(vec[tjm].size() > K) tjm++;
        vec[tjm].push_back({L[i], R[i], i});
        rs[tjm].push_back({R[i], L[i], i});
        sz[tjm].push_back({R[i] - L[i] + 1, L[i], i});
        mnl[tjm] = min(mnl[tjm], L[i]);
        mxl[tjm] = max(mxl[tjm], L[i]);
        gde[i] = tjm;
    }
    for(int i=1; i<=tjm; i++){
        sort(rs[i].begin(), rs[i].end());
        sort(sz[i].begin(), sz[i].end());
    }
}

void ubaci(vector <tuple <ll, int, int>> &vc, tuple <ll, int, int> x){
    for(int i=0; i<vc.size(); i++){
        if(vc[i] > x){
            vc.insert(vc.begin() + i, x);
            return;
        }
    }
    vc.push_back(x);
}

void izbaci(vector <tuple <ll, int, int>> &vc, int x){
    for(int i=0; i<vc.size(); i++){
        if(get<2>(vc[i]) == x){
            vc.erase(vc.begin() + i);
            return;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int T;
    cin >> n >> T;
    int res = 0;
    int tjm = 0;
    int act = 0;
    for(int qry=1; qry<=n; qry++){
        int typ;
        cin >> typ;
        if(typ == 1){
            act++;
            int l, r;
            cin >> l >> r;
            l = (l ^ (T*res));
            r = (r ^ (T*res));
            if(l > r) swap(l, r);
            ++tjm;
            L[tjm] = l;
            R[tjm] = r;
            gde[tjm] = 1;
            for(int i=1; i<=n/K+5; i++){
                if(vec[i].size() == 0) continue;
                gde[tjm] = i;
                if(mxl[i] > L[tjm]) break;
            }
            ubaci(vec[gde[tjm]], {(ll)L[tjm], R[tjm], tjm});
            ubaci(rs[gde[tjm]], {(ll)R[tjm], L[tjm], tjm});
            ubaci(sz[gde[tjm]], {R[tjm] - L[tjm] + 1, L[tjm], tjm});
            mxl[gde[tjm]] = max(mxl[gde[tjm]], L[tjm]);
            mnl[gde[tjm]] = min(mnl[gde[tjm]], L[tjm]);
            if(vec[gde[tjm]].size() > 2*K) Rebuild();
        }
        else if(typ == 2){
            act--;
            int id;
            cin >> id;
            izbaci(vec[gde[id]], id);
            izbaci(rs[gde[id]], id);
            izbaci(sz[gde[id]], id);
        }
        else{
            ll l, r, k;
            cin >> l >> r >> k;
            l = (l ^ (T*res));
            r = (r ^ (T*res));
            if(l > r) swap(l, r);
            res = 0;
            if(k == 0) res = act;
            else{
                if(r - l + 1 >= k) res += query1(l - 1, l + k - 1);
                res += query2(l, r - k + 1, k);
            }
            cout << res << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'void ubaci(std::vector<std::tuple<long long int, int, int> >&, std::tuple<long long int, int, int>)':
segments.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0; i<vc.size(); i++){
      |                  ~^~~~~~~~~~
segments.cpp: In function 'void izbaci(std::vector<std::tuple<long long int, int, int> >&, int)':
segments.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0; i<vc.size(); i++){
      |                  ~^~~~~~~~~~

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