Submission #154968

#	Time	Username	Problem	Language	Result	Execution time	Memory
154968		andrew	Segments (IZhO18_segments)	C++17	100 / 100	4729 ms	15648 KiB

segments

#include <bits/stdc++.h>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
const ll inf = 3e18;
int buben = 2000;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T> void vout(T s){cout << s << endl;exit(0);}

pii a[N + 3];
int stn;

int WD[N + 3];
int Wstn;

pii b[N + 3];
int Stn;

bool f_deleted[N + 3], will_deleted[N + 3];

int luk, ruk;

ll Len_Block, Len;

vector <ll> V[501], V1[501];

void clr(){
    if(!Len)return;
    for(int i = 0; i < Len; i++){
        V[i / Len_Block].clear();
        V1[i / Len_Block].clear();
    }
    Len = 0;
    Len_Block = 0;
}

void build(int Nt){
    Len_Block = 1;
    Len = Nt;
    while(sqr(Len_Block) < Len)Len_Block++;

    for(int i = 0; i < Len; i++){
        V[i / Len_Block].p_b(a[i + 1].se);
        V1[i / Len_Block].p_b(a[i + 1].se - a[i + 1].fi + 1);
    }
    for(int i = 0; i <= (Len - 1) / Len_Block; i++){
        sort(all(V[i]));
        sort(all(V1[i]));
    }
}

int Val;

int V_more(int l, int r){
    l--, r--;
    int ans = 0;
    for(int i = l; i <= r;){
        if(i % Len_Block == 0 && i + Len_Block - 1 <= r){
            ans += (int)V[i / Len_Block].size() - (lower_bound(all(V[i / Len_Block]), Val) - V[i / Len_Block].begin());
            i += Len_Block;
        }else{
            if(a[i + 1].se >= Val)ans++;
            i++;
        }
    }
    return ans;
}

int V1_more(int l, int r){
    l--, r--;
    int ans = 0;
    for(int i = l; i <= r;){
        if(i % Len_Block == 0 && i + Len_Block - 1 <= r){
            ans += (int)V1[i / Len_Block].size() - (lower_bound(all(V1[i / Len_Block]), Val) - V1[i / Len_Block].begin());
            i += Len_Block;
        }else{
            if(a[i + 1].se - a[i + 1].fi + 1 >= Val)ans++;
            i++;
        }
    }
    return ans;
}


struct qry{
    short t;
    int a, b, c, Id;
};

qry c[N + 3];

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    int n, t;
    cin >> n >> t;


    for(int i = 1; i <= n; i++){
        cin >> c[i].t;
        if(c[i].t == 1){
            cin >> c[i].a >> c[i].b;
        }else if(c[i].t == 2){
            cin >> c[i].a;
        }else{
            cin >> c[i].a >> c[i].b >> c[i].c;
        }
    }

    int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k, i, j;
    for(i = 1; i <= n; i++){
        if(i % buben == 0){
            Wstn = 0;
            for(j = i; j <= min(n, i + buben - 1); j++){
                if(c[j].t == 2){
                    will_deleted[c[j].a] = 1;
                    if(c[j].a <= Stn){
                        Wstn++;
                        WD[Wstn] = c[j].a;
                    }
                }
            }
            clr();
            stn = 0;
            for(j = 1; j <= Stn; j++)if(!will_deleted[j]){
                stn++;
                a[stn] = b[j];
            }

            if(stn){
                sort(a + 1, a + stn + 1);
                build(stn);
            }
            l = i;
        }

        if(c[i].t == 1){
            c[i].a ^= t * last_ans;
            c[i].b ^= t * last_ans;
            if(c[i].a > c[i].b)swap(c[i].a, c[i].b);
            Stn++;
            c[i].Id = Stn;
            b[Stn] = {c[i].a, c[i].b};

        }else if(c[i].t == 2){
            f_deleted[c[i].a] = 1;
            will_deleted[c[i].a] = 1;
        }else if(c[i].t == 3){
            c[i].a ^= t * last_ans;
            c[i].b ^= t * last_ans;
            if(c[i].a > c[i].b)swap(c[i].a, c[i].b);
            if(c[i].b - c[i].a + 1 < c[i].c){
                cout << "0\n";
                last_ans = 0;
                continue;
            }
            ans = 0;
            k = c[i].c;
            for(j = l; j < i; j++)if(c[j].t == 1 && !f_deleted[c[j].Id]){
                if(min(c[i].b, c[j].b) - max(c[i].a, c[j].a) + 1 >= c[i].c || c[i].c == 0)ans++;
            }

            for(j = 1; j <= Wstn; j++)if(!f_deleted[WD[j]]){
                if(min(c[i].b, b[WD[j]].se) - max(c[i].a, b[WD[j]].fi) + 1 >= c[i].c || c[i].c == 0)ans++;
            }

            if(!k)ans += stn;
            else{
                if(stn){
                    L = 1, R = stn;
                    while(L < R){
                        mid = (L + R) >> 1;
                        if(a[mid].fi < c[i].a)L = mid + 1; else R = mid;
                    }
                    if(a[L].fi < c[i].a)L++;
                    if(L != 1){
                        Val = k + c[i].a - 1;
                        ans += V_more(1, L - 1);
                    }
                    Le = L;
                    L = 1, R = stn;
                    while(L < R){
                        mid = (L + R) >> 1;
                        if(a[mid].fi <= c[i].b - k + 1)L = mid + 1; else R = mid;
                    }
                    if(a[L].fi <= c[i].b - k + 1)L++;
                    if(Le < L){
                        Val = k;
                        ans += V1_more(Le, L - 1);
                    }
                }

            }
            cout << ans << "\n";
            last_ans = ans;
        }

    }

    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:129:43: warning: unused variable 'Ri' [-Wunused-variable]
     int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k, i, j;
                                           ^~
segments.cpp:129:47: warning: unused variable 'L1' [-Wunused-variable]
     int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k, i, j;
                                               ^~
segments.cpp:129:51: warning: unused variable 'R1' [-Wunused-variable]
     int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k, i, j;
                                                   ^~

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