Submission #805798

#	Time	Username	Problem	Language	Result	Execution time	Memory
805798		farhan132	Segments (IZhO18_segments)	C++17	100 / 100	4027 ms	20804 KiB

segments

/***Farhan132***/
// #pragma GCC optimize("Ofast,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef double dd;
typedef pair<ll , ll> ii;
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clz(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcount(n)
#define clean fflush(stdout)
 
const ll mod =  (ll) 998244353;
// const ll mod =  (ll) 1e9 + 7;
const ll inf = numeric_limits<int>::max()-1;
const ll INF = (ll)2e18;
 
// ll dx[]={0,1,0,-1};
// ll dy[]={1,0,-1,0};
// ll dxx[]={0,1,0,-1,1,1,-1,-1};
// ll dyy[]={1,0,-1,0,1,-1,1,-1};
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll N = 450;

vector < ll > R[450], sz[450];
vector < ii > req[450];
ll lx[450], rx[450], S[450]; ii range[450 * 450];
ll block_cnt = 1;

void add(ll l, ll r){
    for(ll block = 0; block < block_cnt; block++){
        if(lx[block] <= l && l <= rx[block]){
            S[block]++;
            R[block].pb(r);
            sz[block].pb(r - l + 1);
            req[block].pb({l, r});
            for(ll i = S[block] - 1; i >= 1; i--){
                if(R[block][i - 1] > R[block][i]) swap(R[block][i], R[block][i - 1]);
                if(sz[block][i - 1] > sz[block][i]) swap(sz[block][i], sz[block][i - 1]);
                if(req[block][i - 1] > req[block][i]) swap(req[block][i], req[block][i - 1]);
            }
            return;
        }
    }
}
void remove(ll l, ll r){
    // NOTE: must TLE for multiple l
    for(ll block = 0; block < block_cnt; block++){
        if(lx[block] <= l && l <= rx[block]){
            bool done = 0;
            for(ll i = 0; i < req[block].size(); i++){
                if(req[block][i] == make_pair(l, r)){
                    req[block].erase(req[block].begin() + i);
                    done = 1;
                    break;
                }
            }
            if(!done) continue;
            S[block]--;
            for(ll i = 0; i < R[block].size(); i++){
                if(R[block][i] == r){
                    R[block].erase(R[block].begin() + i);
                    break;
                }
            }
            for(ll i = 0; i < sz[block].size(); i++){
                if(sz[block][i] == r - l + 1){
                    sz[block].erase(sz[block].begin() + i);
                    break;
                }
            }
            return;
        }
    }
}
ll query(ll lastans, ll t){
    ll l, r, k; cin >> l >> r >> k;

    l ^= t * lastans;
    r ^= t * lastans;

    if(l > r) swap(l, r);
    if(r - l + 1 < k){
        return 0;
    } 

    ll ans = 0;
    if(k == 0){
        for(ll i = 0; i < block_cnt; i++) ans += req[i].size();
        return ans;
    }

    for(ll i = 0; i < block_cnt; i++){
        if(lx[i] + k - 1 > r) break;
        if(rx[i] <= l){
            if(!S[i]) continue;
            ans += (S[i] - (upper_bound(R[i].begin(), R[i].begin() + S[i], l + k - 2) - R[i].begin()));
            
            // for(auto u : R[i]){
            //     ans += (u >= l + k - 1);
            // }
            continue;
        }
        if(l <= lx[i] && rx[i] + k - 1 <= r){
            if(!S[i]) continue;
            ans += (S[i] - (upper_bound(sz[i].begin(), sz[i].begin() + S[i], k - 1) - sz[i].begin()));            
            continue;
        }

        for(auto [x, y] : req[i]){
            ans += ( (min(y, r) - max(l, x) + 1) >= k);
        }
    }
    return ans;
}
void build(){
    vector < ii > a;
    for(ll i = 0; i < block_cnt; i++){
        for(auto x : req[i]) a.pb(x);
        R[i].clear(); sz[i].clear(); req[i].clear();
        S[i] = 0;
    }
    sort(a.begin(), a.end());
    block_cnt = (a.size() - 1) / N; block_cnt++;
    for(ll i = 0; i < a.size(); i++){
        auto [l, r] = a[i];
        R[i / N].pb(r);
        sz[i / N].pb(r - l + 1);
        req[i / N].pb(a[i]);
        S[i / N]++;
    }

    for(ll i = 0; i < block_cnt; i++){
        sort(R[i].begin(), R[i].end());
        sort(sz[i].begin(), sz[i].end());
    }
    lx[0] = 0; rx[block_cnt - 1] = inf;
    for(ll i = 1; i < block_cnt; i++){
        lx[i] = rx[i - 1] = req[i][0].ff;
    }

    return;
}

void solve(){

    ll n, t; cin >> n >> t;

    ll changes = 0;

    ll cur = 0;
    lx[0] = 0; rx[0] = inf; S[0] = 0;
    ll lastans = 0;
    mem(S, 0);

    while(n--){
        ll T; cin >> T;
        if(T == 1){
            cin >> range[++cur].ff >> range[cur].ss;
            range[cur].ff ^= (t * lastans);
            range[cur].ss ^= (t * lastans);
            if(range[cur].ff > range[cur].ss) swap(range[cur].ff, range[cur].ss);
            add(range[cur].ff, range[cur].ss);
            changes++;
        }
        if(T == 2){
            ll id; cin >> id;
            remove(range[id].ff, range[id].ss);
        }
        if(T == 3){
            lastans = query(lastans, t);
            cout << lastans << '\n';
        }
        if(changes >= N){
            changes = 0;
            build();
        }
    }
    
   return;
}

int main() {

    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        auto start_time = clock();
    #else
         // freopen("subsequence.in", "r", stdin);
         // freopen("subsequence.out", "w", stdout); 
         ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    #endif

    //precalc();
 
    ll T = 1, CT = 0; //cin >> T; 
 
    while(T--){
        // cout << "Case #" << ++CT << ": ";
        solve();
    }
    
    #ifdef LOCAL
        auto end_time = clock();
        cerr<< "Execution time: "<<(end_time - start_time)*(int)1e3/CLOCKS_PER_SEC<<" ms\n";
    #endif
 
    return 0;
} 

Compilation message (stderr)

segments.cpp: In function 'void remove(ll, ll)':
segments.cpp:72:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for(ll i = 0; i < req[block].size(); i++){
      |                           ~~^~~~~~~~~~~~~~~~~~~
segments.cpp:81:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for(ll i = 0; i < R[block].size(); i++){
      |                           ~~^~~~~~~~~~~~~~~~~
segments.cpp:87:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for(ll i = 0; i < sz[block].size(); i++){
      |                           ~~^~~~~~~~~~~~~~~~~~
segments.cpp: In function 'void build()':
segments.cpp:146:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for(ll i = 0; i < a.size(); i++){
      |                   ~~^~~~~~~~~~
segments.cpp: In function 'void solve()':
segments.cpp:180:26: warning: operation on 'cur' may be undefined [-Wsequence-point]
  180 |             cin >> range[++cur].ff >> range[cur].ss;
      |                          ^~~~~
segments.cpp: In function 'int main()':
segments.cpp:218:15: warning: unused variable 'CT' [-Wunused-variable]
  218 |     ll T = 1, CT = 0; //cin >> T;
      |               ^~

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