Submission #893938

#	Time	Username	Problem	Language	Result	Execution time	Memory
893938		skywwla	Segments (IZhO18_segments)	C++17	0 / 100	169 ms	65536 KiB

segments

// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>

#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif

using namespace std ;
using ll = long long ;
using ld = long double ;

struct Node {
    Node *l = nullptr, *r = nullptr ;
    ll low, high ; // []
    ll value = 0 ;
    Node(int L, int R) {low = L, high = R;}
    void update(int i, ll x) {
        if (low == high) {
            value += x ;
        } else {
            int mid = (low + high) / 2 ;
            if (i <= mid) {
                if (!l) l = new Node(low, mid) ;
                l->update(i, x) ;
            } else {
                if (!r) r = new Node(mid + 1, high) ;
                r->update(i, x) ;
            }
            value = 0 ;
            if (l) value += l->value ;
            if (r) value += r->value ;
        }
    }
    ll query(int L, int R) {
        if (L > R) return 0;
        if (high < L || low > R) return 0 ;
        if (L <= low && high <= R) return value;
        ll cur = 0 ;
        if (l) cur += l->query(L, R);
        if (r) cur += r->query(L, R) ;
        return cur ;
    }
};

const int maxn = 3e9, N = 1e6 ;

int idx = 0, sz = 0 ;
pair<int,int> p[N] ;

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    int n , t , qs = 0 ; cin >> n >> t ;
    Node *leftSides = new Node(0, maxn) ;
    Node *rightSides = new Node(0, maxn) ;
    Node *lens = new Node(0, maxn) ;
    auto insert = [&](int L, int R) -> void {
        leftSides->update(L, 1) ;
        rightSides->update(R, 1) ;
        lens->update(R - L + 1, 1) ;
        p[++idx] = {L, R} ;
        sz++ ;
    };
    auto remove = [&](int i) -> void {
        auto [L, R] = p[i] ;
        leftSides->update(L, -1) ;
        rightSides->update(R , -1) ;
        lens->update(R - L + 1, -1) ;
        sz-- ;
    };
    auto query = [&](int L, int R, int k) -> int {
        if ((R - L + 1) < k) {
            qs = 0 ;
            return qs ;
        }
        int _l = L + k - 1 ; _l-- ;
        int _r = R - k + 1 ; _r++ ;
        int ret = sz - lens->query(0, k - 1) ;
        if (_l >= 0) ret -= rightSides->query(0, _l) ;
        if (_r <= maxn) ret -= leftSides->query(_r, maxn) ;
        qs = ret ;
        return qs ;
    };
    for (int i = 0 ; i < n ; i++) {
        int cmd ; cin >> cmd ;
        if (cmd == 1) {
            int a, b; cin >> a >> b ;
            int L = (a ^ (t * qs)) ;
            int R = (b ^ (t * qs)) ;
            if (L > R) swap(L, R) ;
            insert(L, R) ;
        } else if (cmd == 2) {
            int ind ; cin >> ind ;
            remove(ind) ;
        } else {
            int a, b, k ; cin >> a >> b >> k ;
            int L = (a ^ (t * qs)) ;
            int R = (b ^ (t * qs)) ;
            if (L > R) swap(L, R) ;
            cout << query(L, R, k) << "\n" ;
        }
    }
    return 0 ;
}

// 希望白银

Compilation message (stderr)

segments.cpp:48:18: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+9' to '2147483647' [-Woverflow]
   48 | const int maxn = 3e9, N = 1e6 ;
      |                  ^~~

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