oj.uz

답안 #805806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
805806 2023-08-04T00:03:00 Z farhan132 Segments (IZhO18_segments) C++17
16 / 100
 1044 ms 4568 KB 
/***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 int 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] && S[block]){
            auto it = lower_bound(req[block].begin(), req[block].begin() + S[block], make_pair(l, r)); 
            if(it == req[block].end() || *it !=  make_pair(l, r)) continue;
            S[block]--;
            for(ll i = 0; i < req[block].size(); i++){
                if(req[block][i] == make_pair(l, r)){
                    req[block].erase(req[block].begin() + i);
                    break;
                }
            }
            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

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

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Incorrect 9 ms 600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 564 ms 2612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 656 KB Output is correct
2 Correct 33 ms 644 KB Output is correct
3 Correct 78 ms 700 KB Output is correct
4 Correct 37 ms 692 KB Output is correct
5 Correct 768 ms 3816 KB Output is correct
6 Correct 642 ms 2956 KB Output is correct
7 Correct 687 ms 3116 KB Output is correct
8 Correct 1044 ms 4560 KB Output is correct
9 Correct 1006 ms 4516 KB Output is correct
10 Correct 740 ms 3288 KB Output is correct
11 Correct 136 ms 920 KB Output is correct
12 Correct 778 ms 3808 KB Output is correct
13 Correct 677 ms 3420 KB Output is correct
14 Correct 371 ms 1952 KB Output is correct
15 Correct 336 ms 1808 KB Output is correct
16 Correct 253 ms 1352 KB Output is correct
17 Correct 571 ms 2656 KB Output is correct
18 Correct 538 ms 2580 KB Output is correct
19 Correct 536 ms 2704 KB Output is correct
20 Correct 550 ms 2596 KB Output is correct
21 Correct 152 ms 972 KB Output is correct
22 Correct 452 ms 2396 KB Output is correct
23 Correct 561 ms 2792 KB Output is correct
24 Correct 477 ms 2500 KB Output is correct
25 Correct 55 ms 660 KB Output is correct
26 Correct 39 ms 724 KB Output is correct
27 Correct 53 ms 648 KB Output is correct
28 Correct 43 ms 668 KB Output is correct
29 Correct 609 ms 2916 KB Output is correct
30 Correct 616 ms 3012 KB Output is correct
31 Correct 1043 ms 4568 KB Output is correct
32 Correct 742 ms 3260 KB Output is correct
33 Correct 703 ms 3084 KB Output is correct
34 Correct 328 ms 1784 KB Output is correct
35 Correct 567 ms 2752 KB Output is correct
36 Correct 722 ms 3252 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 716 KB Output is correct
2 Correct 38 ms 584 KB Output is correct
3 Correct 37 ms 632 KB Output is correct
4 Correct 52 ms 632 KB Output is correct
5 Incorrect 833 ms 4076 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Incorrect 9 ms 600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Incorrect 9 ms 600 KB Output isn't correct
6 Halted 0 ms 0 KB -