oj.uz

Submission #154926

# Submission time Handle Problem Language Result Execution time Memory
154926 2019-09-25T13:25:17 Z andrew Segments (IZhO18_segments) C++17
7 / 100
 2838 ms 50164 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);
            }
            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 19068 KB Output is correct
3 Correct 24 ms 19320 KB Output is correct
4 Correct 25 ms 19448 KB Output is correct
5 Correct 30 ms 20220 KB Output is correct
6 Correct 33 ms 20244 KB Output is correct
7 Correct 29 ms 19576 KB Output is correct
8 Correct 31 ms 20088 KB Output is correct
9 Correct 35 ms 19952 KB Output is correct
10 Correct 29 ms 20216 KB Output is correct
11 Correct 33 ms 19988 KB Output is correct
12 Correct 32 ms 20088 KB Output is correct
13 Correct 32 ms 20600 KB Output is correct
14 Correct 31 ms 19960 KB Output is correct
15 Correct 24 ms 19420 KB Output is correct
16 Correct 25 ms 19320 KB Output is correct
17 Correct 31 ms 19704 KB Output is correct
18 Correct 29 ms 20216 KB Output is correct
19 Correct 30 ms 19728 KB Output is correct
20 Correct 31 ms 19708 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2219 ms 35168 KB Output is correct
2 Correct 2205 ms 38032 KB Output is correct
3 Correct 2210 ms 37700 KB Output is correct
4 Correct 2375 ms 38532 KB Output is correct
5 Runtime error 2838 ms 50164 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 134 ms 21880 KB Output is correct
2 Correct 120 ms 21696 KB Output is correct
3 Correct 152 ms 23544 KB Output is correct
4 Correct 123 ms 23416 KB Output is correct
5 Runtime error 2617 ms 45992 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 120 ms 21700 KB Output is correct
2 Correct 120 ms 21752 KB Output is correct
3 Correct 124 ms 23656 KB Output is correct
4 Correct 141 ms 23656 KB Output is correct
5 Runtime error 2818 ms 47288 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 19068 KB Output is correct
3 Correct 24 ms 19320 KB Output is correct
4 Correct 25 ms 19448 KB Output is correct
5 Correct 30 ms 20220 KB Output is correct
6 Correct 33 ms 20244 KB Output is correct
7 Correct 29 ms 19576 KB Output is correct
8 Correct 31 ms 20088 KB Output is correct
9 Correct 35 ms 19952 KB Output is correct
10 Correct 29 ms 20216 KB Output is correct
11 Correct 33 ms 19988 KB Output is correct
12 Correct 32 ms 20088 KB Output is correct
13 Correct 32 ms 20600 KB Output is correct
14 Correct 31 ms 19960 KB Output is correct
15 Correct 24 ms 19420 KB Output is correct
16 Correct 25 ms 19320 KB Output is correct
17 Correct 31 ms 19704 KB Output is correct
18 Correct 29 ms 20216 KB Output is correct
19 Correct 30 ms 19728 KB Output is correct
20 Correct 31 ms 19708 KB Output is correct
21 Correct 2219 ms 35168 KB Output is correct
22 Correct 2205 ms 38032 KB Output is correct
23 Correct 2210 ms 37700 KB Output is correct
24 Correct 2375 ms 38532 KB Output is correct
25 Runtime error 2838 ms 50164 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 19068 KB Output is correct
3 Correct 24 ms 19320 KB Output is correct
4 Correct 25 ms 19448 KB Output is correct
5 Correct 30 ms 20220 KB Output is correct
6 Correct 33 ms 20244 KB Output is correct
7 Correct 29 ms 19576 KB Output is correct
8 Correct 31 ms 20088 KB Output is correct
9 Correct 35 ms 19952 KB Output is correct
10 Correct 29 ms 20216 KB Output is correct
11 Correct 33 ms 19988 KB Output is correct
12 Correct 32 ms 20088 KB Output is correct
13 Correct 32 ms 20600 KB Output is correct
14 Correct 31 ms 19960 KB Output is correct
15 Correct 24 ms 19420 KB Output is correct
16 Correct 25 ms 19320 KB Output is correct
17 Correct 31 ms 19704 KB Output is correct
18 Correct 29 ms 20216 KB Output is correct
19 Correct 30 ms 19728 KB Output is correct
20 Correct 31 ms 19708 KB Output is correct
21 Correct 2219 ms 35168 KB Output is correct
22 Correct 2205 ms 38032 KB Output is correct
23 Correct 2210 ms 37700 KB Output is correct
24 Correct 2375 ms 38532 KB Output is correct
25 Runtime error 2838 ms 50164 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
26 Halted 0 ms 0 KB -