Submission #868095

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868095	2023-10-30T12:15:50 Z	sleepntsheep	Segments (IZhO18_segments)	C++17	16 / 100	1568 ms	7260 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;
    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;
}

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));
    V = 99999;


    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:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d%d", &n, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%d%d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |             scanf("%d", &y);
      |             ~~~~~^~~~~~~~~~
segments.cpp:81:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |             scanf("%d%d", &y, &k); z=0;
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1554 ms	7260 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	694 ms	6664 KB	Output is correct
2	Correct	690 ms	6900 KB	Output is correct
3	Correct	701 ms	6592 KB	Output is correct
4	Correct	695 ms	6840 KB	Output is correct
5	Correct	1258 ms	6836 KB	Output is correct
6	Correct	1524 ms	6732 KB	Output is correct
7	Correct	1373 ms	6764 KB	Output is correct
8	Correct	335 ms	6584 KB	Output is correct
9	Correct	211 ms	6580 KB	Output is correct
10	Correct	560 ms	6616 KB	Output is correct
11	Correct	711 ms	6740 KB	Output is correct
12	Correct	556 ms	6628 KB	Output is correct
13	Correct	645 ms	6648 KB	Output is correct
14	Correct	779 ms	6736 KB	Output is correct
15	Correct	777 ms	6820 KB	Output is correct
16	Correct	770 ms	6844 KB	Output is correct
17	Correct	1568 ms	7004 KB	Output is correct
18	Correct	1553 ms	7000 KB	Output is correct
19	Correct	1552 ms	7228 KB	Output is correct
20	Correct	1516 ms	7092 KB	Output is correct
21	Correct	717 ms	6936 KB	Output is correct
22	Correct	765 ms	6676 KB	Output is correct
23	Correct	704 ms	6656 KB	Output is correct
24	Correct	768 ms	6756 KB	Output is correct
25	Correct	688 ms	6840 KB	Output is correct
26	Correct	688 ms	6736 KB	Output is correct
27	Correct	704 ms	6864 KB	Output is correct
28	Correct	683 ms	7176 KB	Output is correct
29	Correct	665 ms	6488 KB	Output is correct
30	Correct	662 ms	6492 KB	Output is correct
31	Correct	192 ms	6832 KB	Output is correct
32	Correct	554 ms	6608 KB	Output is correct
33	Correct	613 ms	6600 KB	Output is correct
34	Correct	787 ms	6800 KB	Output is correct
35	Correct	710 ms	6888 KB	Output is correct
36	Correct	573 ms	6488 KB	Output is correct