Submission #868091

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868091	2023-10-30T12:02:25 Z	sleepntsheep	Segments (IZhO18_segments)	C++17	16 / 100	832 ms	19916 KB

segments

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

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

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

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

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;
    return a[aa].r - a[bb].r;
}

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;
    return a[aa].l - a[bb].l;
}

void rebuild()
{
    for (; nc;) a[na++] = c[--nc];
    qsort(a, na, sizeof *a, compare_length);
    for (int i = 0; i * V <= na; ++i) sz[i] = 0;
    for (int i = 0; i < na; ++i) e[i/V][sz[i/V]] = f[i/V][sz[i/V]] = i, ++sz[i/V];
    for (int i = 0; i * V <= na; ++i)
    {
        qsort(e[i], sz[i], sizeof **e, compare_left_increasing_index);
        qsort(f[i], sz[i], sizeof **f, compare_right_increasing_index);
        we[i][sz[i]] = 0;
        for (int j = sz[i]; j--;) we[i][j] = we[i][j+1] + a[e[i][j]].w;
        wf[i][0] = a[f[i][0]].w;
        for (int j = 1; j < sz[i]; ++j) wf[i][j] = wf[i][j-1] + a[f[i][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 + 1 < k || r - j->l + 1 < k) 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][M]].l > r - k + 1) R = M - 1, cnt = we[j][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][M]].r < k + l - 1) L = M + 1, cnt = wf[j][M];
                            else R = M - 1;
                        }
                        z -= cnt;
                    }
                }
            }

            /* count in buffer */
            for (struct line *j = c; j < c + nc; ++j) if (j->r - l + 1 < k || r - j->l + 1 < k) z -= j->w;

            lastans = (z += S);
            printf("%d\n", z);
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	12632 KB	Output is correct
2	Correct	1 ms	12636 KB	Output is correct
3	Incorrect	7 ms	12812 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	516 ms	17396 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	467 ms	17456 KB	Output is correct
2	Correct	489 ms	17672 KB	Output is correct
3	Correct	480 ms	17484 KB	Output is correct
4	Correct	484 ms	17440 KB	Output is correct
5	Correct	721 ms	17732 KB	Output is correct
6	Correct	671 ms	17508 KB	Output is correct
7	Correct	713 ms	17408 KB	Output is correct
8	Correct	825 ms	17748 KB	Output is correct
9	Correct	832 ms	19828 KB	Output is correct
10	Correct	797 ms	19804 KB	Output is correct
11	Correct	501 ms	19400 KB	Output is correct
12	Correct	791 ms	19644 KB	Output is correct
13	Correct	727 ms	19464 KB	Output is correct
14	Correct	598 ms	19500 KB	Output is correct
15	Correct	592 ms	19520 KB	Output is correct
16	Correct	533 ms	19472 KB	Output is correct
17	Correct	619 ms	19492 KB	Output is correct
18	Correct	596 ms	19608 KB	Output is correct
19	Correct	603 ms	19876 KB	Output is correct
20	Correct	595 ms	19416 KB	Output is correct
21	Correct	524 ms	19452 KB	Output is correct
22	Correct	680 ms	19828 KB	Output is correct
23	Correct	737 ms	19716 KB	Output is correct
24	Correct	697 ms	19536 KB	Output is correct
25	Correct	479 ms	19344 KB	Output is correct
26	Correct	476 ms	19340 KB	Output is correct
27	Correct	466 ms	19292 KB	Output is correct
28	Correct	497 ms	19364 KB	Output is correct
29	Correct	745 ms	19608 KB	Output is correct
30	Correct	752 ms	19656 KB	Output is correct
31	Correct	830 ms	19916 KB	Output is correct
32	Correct	783 ms	19904 KB	Output is correct
33	Correct	746 ms	19668 KB	Output is correct
34	Correct	572 ms	19524 KB	Output is correct
35	Correct	672 ms	19580 KB	Output is correct
36	Correct	757 ms	19808 KB	Output is correct