oj.uz

Submission #154930

# Submission time Handle Problem Language Result Execution time Memory
154930 2019-09-25T13:36:14 Z andrew Segments (IZhO18_segments) C++17
7 / 100
 2879 ms 48056 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);
}

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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 20 ms 19192 KB Output is correct
3 Correct 24 ms 19320 KB Output is correct
4 Correct 22 ms 19320 KB Output is correct
5 Correct 34 ms 20088 KB Output is correct
6 Correct 31 ms 20088 KB Output is correct
7 Correct 27 ms 19448 KB Output is correct
8 Correct 30 ms 19960 KB Output is correct
9 Correct 30 ms 19960 KB Output is correct
10 Correct 31 ms 20088 KB Output is correct
11 Correct 33 ms 19960 KB Output is correct
12 Correct 31 ms 19960 KB Output is correct
13 Correct 36 ms 20472 KB Output is correct
14 Correct 33 ms 19920 KB Output is correct
15 Correct 27 ms 19320 KB Output is correct
16 Correct 24 ms 19320 KB Output is correct
17 Correct 29 ms 19568 KB Output is correct
18 Correct 33 ms 20088 KB Output is correct
19 Correct 28 ms 19576 KB Output is correct
20 Correct 32 ms 19576 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2312 ms 34904 KB Output is correct
2 Correct 2333 ms 35124 KB Output is correct
3 Correct 2596 ms 34964 KB Output is correct
4 Correct 2426 ms 35800 KB Output is correct
5 Runtime error 2879 ms 48056 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 105 ms 21624 KB Output is correct
2 Correct 97 ms 21624 KB Output is correct
3 Correct 119 ms 21624 KB Output is correct
4 Correct 97 ms 21584 KB Output is correct
5 Runtime error 2665 ms 43644 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 95 ms 21496 KB Output is correct
2 Correct 98 ms 21608 KB Output is correct
3 Correct 97 ms 21624 KB Output is correct
4 Correct 104 ms 21672 KB Output is correct
5 Runtime error 2851 ms 44776 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 19 ms 19192 KB Output is correct
2 Correct 20 ms 19192 KB Output is correct
3 Correct 24 ms 19320 KB Output is correct
4 Correct 22 ms 19320 KB Output is correct
5 Correct 34 ms 20088 KB Output is correct
6 Correct 31 ms 20088 KB Output is correct
7 Correct 27 ms 19448 KB Output is correct
8 Correct 30 ms 19960 KB Output is correct
9 Correct 30 ms 19960 KB Output is correct
10 Correct 31 ms 20088 KB Output is correct
11 Correct 33 ms 19960 KB Output is correct
12 Correct 31 ms 19960 KB Output is correct
13 Correct 36 ms 20472 KB Output is correct
14 Correct 33 ms 19920 KB Output is correct
15 Correct 27 ms 19320 KB Output is correct
16 Correct 24 ms 19320 KB Output is correct
17 Correct 29 ms 19568 KB Output is correct
18 Correct 33 ms 20088 KB Output is correct
19 Correct 28 ms 19576 KB Output is correct
20 Correct 32 ms 19576 KB Output is correct
21 Correct 2312 ms 34904 KB Output is correct
22 Correct 2333 ms 35124 KB Output is correct
23 Correct 2596 ms 34964 KB Output is correct
24 Correct 2426 ms 35800 KB Output is correct
25 Runtime error 2879 ms 48056 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 19 ms 19192 KB Output is correct
2 Correct 20 ms 19192 KB Output is correct
3 Correct 24 ms 19320 KB Output is correct
4 Correct 22 ms 19320 KB Output is correct
5 Correct 34 ms 20088 KB Output is correct
6 Correct 31 ms 20088 KB Output is correct
7 Correct 27 ms 19448 KB Output is correct
8 Correct 30 ms 19960 KB Output is correct
9 Correct 30 ms 19960 KB Output is correct
10 Correct 31 ms 20088 KB Output is correct
11 Correct 33 ms 19960 KB Output is correct
12 Correct 31 ms 19960 KB Output is correct
13 Correct 36 ms 20472 KB Output is correct
14 Correct 33 ms 19920 KB Output is correct
15 Correct 27 ms 19320 KB Output is correct
16 Correct 24 ms 19320 KB Output is correct
17 Correct 29 ms 19568 KB Output is correct
18 Correct 33 ms 20088 KB Output is correct
19 Correct 28 ms 19576 KB Output is correct
20 Correct 32 ms 19576 KB Output is correct
21 Correct 2312 ms 34904 KB Output is correct
22 Correct 2333 ms 35124 KB Output is correct
23 Correct 2596 ms 34964 KB Output is correct
24 Correct 2426 ms 35800 KB Output is correct
25 Runtime error 2879 ms 48056 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
26 Halted 0 ms 0 KB -