Submission #868096

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868096	2023-10-30T12:18:22 Z	sleepntsheep	Segments (IZhO18_segments)	C++17	16 / 100	848 ms	10180 KB

segments

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define N 200005
#define V0 6666
int V;

int n, t, na, nc, S, id = 1;
struct line { int l, r, w; } a[N], c[N], o[N];
int e[N], f[N], we[N], wf[N], sz[V0];

int compare_length(const void *a0, const void *b0)
{
    const struct line *a = (const struct line*)a0, *b = (const struct line*)b0;
    if (a->r - a->l != b->r - b->l) return ((a->r - a->l) - (b->r - b->l));
    if (a->l != b->l) return a->l - b->l;
    return a->w - b->w;
}

int compare_left_increasing_index(const void *a0, const void *b0)
{
    const int aa = *(const int*)a0, bb = *(const int*)b0;
    if (a[aa].l != a[bb].l) return a[aa].l - a[bb].l;
    if (a[aa].r != a[bb].r) return a[aa].r - a[bb].r;
    return a[aa].w - a[bb].w;
}

int compare_right_increasing_index(const void *a0, const void *b0)
{
    const int aa = *(const int*)a0, bb = *(const int*)b0;
    if (a[aa].r != a[bb].r) return a[aa].r - a[bb].r;
    if (a[aa].l != a[bb].l) return a[aa].l - a[bb].l;
    return a[aa].w - a[bb].w;
}

inline void rebuild()
{
    for (; nc;) a[na++] = c[--nc];
    qsort(a, na, sizeof *a, compare_length);
    memset(sz, 0, sizeof *sz * (na / V + 1));
    for (int i = 0; i < na; ++i) e[i] = f[i] = i, ++sz[i/V];
    for (int i = 0; i * V <= na; ++i)
    {
        qsort(e+i*V, sz[i], sizeof *e, compare_left_increasing_index);
        qsort(f+i*V, sz[i], sizeof *f, compare_right_increasing_index);

        we[i*V+sz[i]-1] = a[e[i*V+sz[i]-1]].w;
        for (int j = i*V+sz[i]-1; --j >= i*V;) we[j] = we[j+1] + a[e[j]].w;
        wf[i*V] = a[f[i*V]].w;
        for (int j = i*V+1; j < i*V+sz[i]; ++j) wf[j] = wf[j-1] + a[f[j]].w;
    }
}

int main(void)
{
    scanf("%d%d", &n, &t);
    V = sqrt(n * log2(n));


    for (int z = 0, lastans = 0, op, x, y, k, l, r; n--;)
    {
        scanf("%d%d", &op, &x);
        if (op == 1)
        {
            scanf("%d", &y);
            l = x ^ (t * lastans), r = y ^ (t * lastans);
            if (l>r) { int t=l;l=r;r=t;}
            o[id++] = c[nc++] = (struct line){l, r, 1};
            if (nc == V) rebuild();
            ++S;
        }
        else if (op == 2)
        {
            c[nc++] = (struct line){o[x].l, o[x].r, -1};
            if (nc == V) rebuild();
            --S;
        }
        else
        {
            scanf("%d%d", &y, &k); z=0;
            l = x ^ (t * lastans), r = y ^ (t * lastans);
            if (l>r) { int t=l;l=r;r=t;}
            /* count in static */
            {
                int Z = -1;
                for (int L = 0, R = na-1; L <= R; )
                {
                    int M = (L+R)/2;
                    if (a[M].r - a[M].l + 1 >= k) R = M - 1, Z = M;
                    else L = M + 1;
                }
                if (Z != -1)
                {
                    int zb = Z/V, sb = zb+1;
                    for (struct line *j = a + Z; j < a + sb * V; ++j) if (j->r < l + k - 1 || j->l > r - k + 1) z -= j->w;
                    for (int j = sb; j * V <= na; ++j)
                    {
                        /* r - j->l + 1 < k === j->l > r - k + 1 */
                        int cnt = 0;
                        for (int L = 0, R = sz[j]-1; L <= R;)
                        {
                            int M = (L+R)/2;
                            if (a[e[j*V+M]].l > r - k + 1) R = M - 1, cnt = we[j*V+M];
                            else L = M + 1;
                        }
                        z -= cnt;
                        cnt = 0;
                        /* j->r - l + 1 < k === j->l < k + l - 1 */
                        for (int L = 0, R = sz[j]-1; L <= R;)
                        {
                            int M = (L+R)/2;
                            if (a[f[j*V+M]].r < k + l - 1) L = M + 1, cnt = wf[j*V+M];
                            else R = M - 1;
                        }
                        z -= cnt;
                    }
                }
            }

            /* count in buffer */
            for (struct line *j = c; j < c + nc; ++j) if (j->r < l + k - 1 || j->l > r - k + 1) z -= j->w;
            lastans = (z += S);
            printf("%d\n", z);
        }
    }
    return 0;
}

Compilation message

segments.cpp: In function 'int main()':
segments.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d%d", &n, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d%d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:69:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |             scanf("%d", &y);
      |             ~~~~~^~~~~~~~~~
segments.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |             scanf("%d%d", &y, &k); z=0;
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6488 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Incorrect	6 ms	6492 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	505 ms	9368 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	487 ms	9708 KB	Output is correct
2	Correct	485 ms	9788 KB	Output is correct
3	Correct	476 ms	9680 KB	Output is correct
4	Correct	492 ms	9892 KB	Output is correct
5	Correct	755 ms	9636 KB	Output is correct
6	Correct	693 ms	9480 KB	Output is correct
7	Correct	701 ms	9500 KB	Output is correct
8	Correct	829 ms	9932 KB	Output is correct
9	Correct	847 ms	9952 KB	Output is correct
10	Correct	790 ms	9960 KB	Output is correct
11	Correct	529 ms	9720 KB	Output is correct
12	Correct	828 ms	9996 KB	Output is correct
13	Correct	762 ms	9924 KB	Output is correct
14	Correct	609 ms	10000 KB	Output is correct
15	Correct	581 ms	9808 KB	Output is correct
16	Correct	557 ms	9772 KB	Output is correct
17	Correct	605 ms	9340 KB	Output is correct
18	Correct	615 ms	9364 KB	Output is correct
19	Correct	593 ms	9372 KB	Output is correct
20	Correct	593 ms	9384 KB	Output is correct
21	Correct	541 ms	9756 KB	Output is correct
22	Correct	727 ms	9788 KB	Output is correct
23	Correct	760 ms	9808 KB	Output is correct
24	Correct	699 ms	9784 KB	Output is correct
25	Correct	477 ms	9824 KB	Output is correct
26	Correct	479 ms	9856 KB	Output is correct
27	Correct	472 ms	9700 KB	Output is correct
28	Correct	485 ms	9684 KB	Output is correct
29	Correct	762 ms	9856 KB	Output is correct
30	Correct	756 ms	9976 KB	Output is correct
31	Correct	848 ms	10036 KB	Output is correct
32	Correct	820 ms	9748 KB	Output is correct
33	Correct	747 ms	10180 KB	Output is correct
34	Correct	610 ms	9776 KB	Output is correct
35	Correct	725 ms	9748 KB	Output is correct
36	Correct	773 ms	9956 KB	Output is correct