oj.uz

Submission #154928

# Submission time Handle Problem Language Result Execution time Memory
154928 2019-09-25T13:27:32 Z andrew Segments (IZhO18_segments) C++17
7 / 100
 3104 ms 48200 KB 
#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);
}

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

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

    vector <qry> c(n + 1);

    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;
    for(int i = 1; i <= n; i++){
        if(i % buben == 0){
            Wstn = 0;
            for(int 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);
//            }
            for(int j = 1; j <= 4 * N + 2; j++){
                V[j].clear();
                V1[j].clear();
            }
            stn = 0;
            for(int 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(int 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(int 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

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;
                                           ^~
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;
                                               ^~
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;
                                                   ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 19 ms 19196 KB Output is correct
3 Correct 30 ms 19320 KB Output is correct
4 Correct 32 ms 19320 KB Output is correct
5 Correct 39 ms 20216 KB Output is correct
6 Correct 41 ms 20164 KB Output is correct
7 Correct 37 ms 19448 KB Output is correct
8 Correct 39 ms 20056 KB Output is correct
9 Correct 42 ms 20072 KB Output is correct
10 Correct 38 ms 20344 KB Output is correct
11 Correct 45 ms 19960 KB Output is correct
12 Correct 44 ms 20016 KB Output is correct
13 Correct 45 ms 20604 KB Output is correct
14 Correct 40 ms 20088 KB Output is correct
15 Correct 33 ms 19320 KB Output is correct
16 Correct 33 ms 19320 KB Output is correct
17 Correct 39 ms 19704 KB Output is correct
18 Correct 38 ms 20220 KB Output is correct
19 Correct 40 ms 19704 KB Output is correct
20 Correct 43 ms 19752 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2630 ms 35240 KB Output is correct
2 Correct 2663 ms 35180 KB Output is correct
3 Correct 2962 ms 35244 KB Output is correct
4 Correct 2609 ms 35908 KB Output is correct
5 Runtime error 3104 ms 48200 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 21932 KB Output is correct
2 Correct 316 ms 21792 KB Output is correct
3 Correct 340 ms 21880 KB Output is correct
4 Correct 306 ms 21752 KB Output is correct
5 Runtime error 2902 ms 43768 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 21928 KB Output is correct
2 Correct 301 ms 21724 KB Output is correct
3 Correct 338 ms 21852 KB Output is correct
4 Correct 328 ms 21752 KB Output is correct
5 Runtime error 2996 ms 44692 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 19 ms 19196 KB Output is correct
3 Correct 30 ms 19320 KB Output is correct
4 Correct 32 ms 19320 KB Output is correct
5 Correct 39 ms 20216 KB Output is correct
6 Correct 41 ms 20164 KB Output is correct
7 Correct 37 ms 19448 KB Output is correct
8 Correct 39 ms 20056 KB Output is correct
9 Correct 42 ms 20072 KB Output is correct
10 Correct 38 ms 20344 KB Output is correct
11 Correct 45 ms 19960 KB Output is correct
12 Correct 44 ms 20016 KB Output is correct
13 Correct 45 ms 20604 KB Output is correct
14 Correct 40 ms 20088 KB Output is correct
15 Correct 33 ms 19320 KB Output is correct
16 Correct 33 ms 19320 KB Output is correct
17 Correct 39 ms 19704 KB Output is correct
18 Correct 38 ms 20220 KB Output is correct
19 Correct 40 ms 19704 KB Output is correct
20 Correct 43 ms 19752 KB Output is correct
21 Correct 2630 ms 35240 KB Output is correct
22 Correct 2663 ms 35180 KB Output is correct
23 Correct 2962 ms 35244 KB Output is correct
24 Correct 2609 ms 35908 KB Output is correct
25 Runtime error 3104 ms 48200 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
26 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 19 ms 19196 KB Output is correct
3 Correct 30 ms 19320 KB Output is correct
4 Correct 32 ms 19320 KB Output is correct
5 Correct 39 ms 20216 KB Output is correct
6 Correct 41 ms 20164 KB Output is correct
7 Correct 37 ms 19448 KB Output is correct
8 Correct 39 ms 20056 KB Output is correct
9 Correct 42 ms 20072 KB Output is correct
10 Correct 38 ms 20344 KB Output is correct
11 Correct 45 ms 19960 KB Output is correct
12 Correct 44 ms 20016 KB Output is correct
13 Correct 45 ms 20604 KB Output is correct
14 Correct 40 ms 20088 KB Output is correct
15 Correct 33 ms 19320 KB Output is correct
16 Correct 33 ms 19320 KB Output is correct
17 Correct 39 ms 19704 KB Output is correct
18 Correct 38 ms 20220 KB Output is correct
19 Correct 40 ms 19704 KB Output is correct
20 Correct 43 ms 19752 KB Output is correct
21 Correct 2630 ms 35240 KB Output is correct
22 Correct 2663 ms 35180 KB Output is correct
23 Correct 2962 ms 35244 KB Output is correct
24 Correct 2609 ms 35908 KB Output is correct
25 Runtime error 3104 ms 48200 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
26 Halted 0 ms 0 KB -