Submission #154930

#	Time	Username	Problem	Language	Result	Execution time	Memory
154930		andrew	Segments (IZhO18_segments)	C++17	7 / 100	2879 ms	48056 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 = 1e5;
const ll inf = 3e18;
int buben = 1000;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

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

vector <int> V[4 * N + 3], V1[4 * N + 3];
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];

void clr(int v, int tl, int tr){
    V[v].clear();
    V1[v].clear();
    if(tl != tr){
        clr(v << 1, tl, ((tl + tr) >> 1));
        clr((v << 1) + 1, ((tl + tr) >> 1) + 1, tr);
    }
}

int luk, ruk;

void build(int v, int tl, int tr){
    if(tl == tr){
        V[v].p_b(a[tl].se);
        V1[v].p_b(a[tl].se - a[tl].fi + 1);
    }else{
        build(v << 1, tl, ((tl + tr) >> 1));
        build((v << 1) + 1, ((tl + tr) >> 1) + 1, tr);

        luk = 0;
        ruk = 0;

        while(luk < V[v << 1].size() && ruk < V[(v << 1) + 1].size()){
            if(V[v << 1][luk] < V[(v << 1) + 1][ruk]){
                V[v].p_b(V[v << 1][luk]);
                luk++;
            }else{
                V[v].p_b(V[(v << 1) + 1][ruk]);
                ruk++;
            }
        }

        while(luk < V[v << 1].size()){
            V[v].p_b(V[v << 1][luk]);
            luk++;
        }

        while(ruk < V[(v << 1) + 1].size()){
            V[v].p_b(V[(v << 1) + 1][ruk]);
            ruk++;
        }

        luk = 0;
        ruk = 0;
        while(luk < V1[v << 1].size() && ruk < V1[(v << 1) + 1].size()){
            if(V1[v << 1][luk] < V1[(v << 1) + 1][ruk]){
                V1[v].p_b(V1[v << 1][luk]);
                luk++;
            }else{
                V1[v].p_b(V1[(v << 1) + 1][ruk]);
                ruk++;
            }
        }

        while(luk < V1[v << 1].size()){
            V1[v].p_b(V1[v << 1][luk]);
            luk++;
        }

        while(ruk < V1[(v << 1) + 1].size()){
            V1[v].p_b(V1[(v << 1) + 1][ruk]);
            ruk++;
        }

    }
}

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

int Val;

int V_more(int v, int tl, int tr, int l, int r){
    if(l > r)return 0;
    if(tl == l && tr == r){
        return (int)V[v].size() - (lower_bound(all(V[v]), Val) - V[v].begin());
    }
    return V_more(v << 1, tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1))) + V_more((v << 1) + 1, ((tl + tr) >> 1) + 1, tr, max(l, ((tl + tr) >> 1) + 1), r);
}

int V1_more(int v, int tl, int tr, int l, int r){
    if(l > r)return 0;
    if(tl == l && tr == r){
        return (int)V1[v].size() - (lower_bound(all(V1[v]), Val) - V1[v].begin());
    }
    return V1_more(v << 1, tl, ((tl + tr) >> 1), l, min(r, ((tl + tr) >> 1))) + V1_more((v << 1) + 1, ((tl + tr) >> 1) + 1, tr, max(l, ((tl + tr) >> 1) + 1), r);
}

qry c[N + 3];

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

    //while(sqr(buben) < n)buben++;
    //buben = 2501;

    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;
                    }
                }
            }
            if(stn){
                clr(1, 1, stn);
            }
            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(1, 1, 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, 1, stn, 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(1, 1, stn, Le, L - 1);
                    }
                }

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

    }

    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'void build(int, int, int)':
segments.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(luk < V[v << 1].size() && ruk < V[(v << 1) + 1].size()){
               ~~~~^~~~~~~~~~~~~~~~~~
segments.cpp:63:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(luk < V[v << 1].size() && ruk < V[(v << 1) + 1].size()){
                                         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(luk < V[v << 1].size()){
               ~~~~^~~~~~~~~~~~~~~~~~
segments.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ruk < V[(v << 1) + 1].size()){
               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(luk < V1[v << 1].size() && ruk < V1[(v << 1) + 1].size()){
               ~~~~^~~~~~~~~~~~~~~~~~~
segments.cpp:85:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(luk < V1[v << 1].size() && ruk < V1[(v << 1) + 1].size()){
                                          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(luk < V1[v << 1].size()){
               ~~~~^~~~~~~~~~~~~~~~~~~
segments.cpp:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ruk < V1[(v << 1) + 1].size()){
               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:153: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:153: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:153: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: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25