Submission #1130893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130893		Gray	Segments (IZhO18_segments)	C++17	7 / 100	5093 ms	3168 KiB

segments

#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

const ll INF = 2e18;
const ll MOD = 1e9+7;

ll block_sz=2, upd_sz=2;

struct ranges{
    struct block{
        vector<ll> by_r, by_l;
    };
    vector<block> a;
    vector<pair<ll, ll>> all;
    vector<pair<ll, ll>> upd;
    ll n, block_cnt;

    void apply_upd(){
        for (auto ch:upd) all.push_back(ch);
        n=all.size(); upd.clear();
        block_cnt = n/block_sz+(n%block_sz?1:0);
        a.clear(); a.resize(block_cnt);
        sort(all.begin(), all.end(), [](auto &op1, auto &op2){
            return op1.ss-op1.ff<op2.ss-op2.ff;
        });
        for (ll i=0; i<n; i++){
            a[i/block_sz].by_r.push_back(all[i].ss);
            a[i/block_sz].by_l.push_back(all[i].ff);
        }
        for (ll i=0; i<block_cnt; i++){
            sort(a[i].by_r.begin(), a[i].by_r.end());
            sort(a[i].by_l.begin(), a[i].by_l.end());
        }
    }

    void add(ll l, ll r){
        upd.push_back({l, r});
        if ((ll)upd.size()>upd_sz) apply_upd();
    }

    ll _query(ll l, ll r, ll k){
        ll res=0;
        if (!a.empty()){
            ll ind = lower_bound(all.begin(), all.end(), mp(1, k), [](auto op1, auto op2){ return op1.ss-op1.ff<op2.ss-op2.ff;})-all.begin();
            ll block_num = ind/block_sz;

            res = n-ind;
            for (ll i=block_num+1; i<block_cnt; i++){
                res-=upper_bound(a[i].by_r.begin(), a[i].by_r.end(), l+k-2)-a[i].by_r.begin();
                res-=a[i].by_l.end()-upper_bound(a[i].by_l.begin(), a[i].by_l.end(), r-k+1);
            }
            for (ll i=ind; i<min(n, (block_num+1)*block_sz); i++){
                if (min(all[i].ss, r)-max(all[i].ff, l)+1<k) res--;
            }
        }
        for (auto &ch:upd){
            if (min(ch.ss, r)-max(ch.ff, l)+1>=k) res++;
        }
        return res;
    }
    ll query(ll l, ll r, ll k){
        if (k) return _query(l, r, k);
        else return upd.size()+n-query(l, r, 1);
    }
};

void solve(){
    ll n, t; cin >> n >> t;
    ranges incl, excl;
    ll lastans=0;
    vector<pair<ll, ll>> ids;
    while (n--){
        ll type; cin >> type;
        if (type==1){
            ll a, b; cin >> a >> b;
            ll l=a^(t*lastans), r = b^(t*lastans);
            if (l>r) swap(l, r);
            incl.add(l, r);
            ids.push_back({l, r});
            // cout << "Add: " << l << "-" << r << ln;
        }else if (type==2){
            ll id; cin >> id; id--;
            excl.add(ids[id].ff, ids[id].ss);
        }else{
            ll a, b, k; cin >> a >> b >> k;
            ll l=a^(t*lastans), r = b^(t*lastans);
            if (l>r) swap(l, r);
            // cout << l << "-" << r << ":";
            lastans = incl.query(l, r, k)-excl.query(l, r, k);
            // cout << incl.query(l, r, k) << "&" << excl.query(l, r, k) << " -> ";
            cout << lastans << ln;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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