oj.uz

Submission #805787

# Submission time Handle Problem Language Result Execution time Memory
805787 2023-08-03T23:31:36 Z farhan132 Segments (IZhO18_segments) C++17
16 / 100
 1073 ms 4600 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]){
            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] - (lower_bound(R[i].begin(), R[i].end(), l + k - 1) - R[i].begin()));
            continue;
        }
        if(l <= lx[i] && rx[i] + k - 1 <= r){
            if(!S[i]) continue;
            ans += (S[i] - (lower_bound(sz[i].begin(), sz[i].end(), k) - 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:72: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]
   72 |             for(ll i = 0; i < req[block].size(); i++){
      |                           ~~^~~~~~~~~~~~~~~~~~~
segments.cpp:81:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<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 'int'} and 'std::vector<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:142: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]
  142 |     for(ll i = 0; i < a.size(); i++){
      |                   ~~^~~~~~~~~~
segments.cpp: In function 'void solve()':
segments.cpp:176:26: warning: operation on 'cur' may be undefined [-Wsequence-point]
  176 |             cin >> range[++cur].ff >> range[cur].ss;
      |                          ^~~~~
segments.cpp: In function 'int main()':
segments.cpp:214:15: warning: unused variable 'CT' [-Wunused-variable]
  214 |     ll T = 1, CT = 0; //cin >> T;
      |               ^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Incorrect 9 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 575 ms 2488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 712 KB Output is correct
2 Correct 32 ms 708 KB Output is correct
3 Correct 75 ms 732 KB Output is correct
4 Correct 46 ms 756 KB Output is correct
5 Correct 783 ms 3876 KB Output is correct
6 Correct 649 ms 2904 KB Output is correct
7 Correct 705 ms 3028 KB Output is correct
8 Correct 1073 ms 4600 KB Output is correct
9 Correct 1002 ms 4532 KB Output is correct
10 Correct 767 ms 3276 KB Output is correct
11 Correct 138 ms 1056 KB Output is correct
12 Correct 784 ms 3816 KB Output is correct
13 Correct 660 ms 3008 KB Output is correct
14 Correct 380 ms 1932 KB Output is correct
15 Correct 334 ms 1828 KB Output is correct
16 Correct 259 ms 1432 KB Output is correct
17 Correct 544 ms 2484 KB Output is correct
18 Correct 555 ms 2748 KB Output is correct
19 Correct 548 ms 2700 KB Output is correct
20 Correct 545 ms 2516 KB Output is correct
21 Correct 172 ms 944 KB Output is correct
22 Correct 444 ms 2440 KB Output is correct
23 Correct 595 ms 2720 KB Output is correct
24 Correct 472 ms 2500 KB Output is correct
25 Correct 53 ms 720 KB Output is correct
26 Correct 38 ms 640 KB Output is correct
27 Correct 54 ms 676 KB Output is correct
28 Correct 42 ms 652 KB Output is correct
29 Correct 613 ms 2888 KB Output is correct
30 Correct 618 ms 2924 KB Output is correct
31 Correct 1008 ms 4532 KB Output is correct
32 Correct 742 ms 3356 KB Output is correct
33 Correct 686 ms 3096 KB Output is correct
34 Correct 330 ms 1800 KB Output is correct
35 Correct 597 ms 2740 KB Output is correct
36 Correct 724 ms 3164 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 644 KB Output is correct
2 Correct 34 ms 628 KB Output is correct
3 Correct 34 ms 700 KB Output is correct
4 Correct 40 ms 660 KB Output is correct
5 Incorrect 852 ms 3980 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Incorrect 9 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Incorrect 9 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -