Submission #868100

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868100	2023-10-30T12:32:49 Z	sleepntsheep	Segments (IZhO18_segments)	C++17	16 / 100	888 ms	10172 KB

segments

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

#include <assert.h>
#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];

inline int max(int a, int b)  { return b>a?b:a; }
inline int min(int a, int b)  { return b<a?b:a; }

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 - 1) 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 (min(j->r, r) - max(j->l, l) + 1 < k) z -= j->w;
                //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:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d%d", &n, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d%d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |             scanf("%d", &y);
      |             ~~~~~^~~~~~~~~~
segments.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |             scanf("%d%d", &y, &k); z=0;
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	524 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	486 ms	10172 KB	Output is correct
2	Correct	484 ms	9660 KB	Output is correct
3	Correct	490 ms	9728 KB	Output is correct
4	Correct	480 ms	9644 KB	Output is correct
5	Correct	723 ms	9624 KB	Output is correct
6	Correct	672 ms	9680 KB	Output is correct
7	Correct	700 ms	9672 KB	Output is correct
8	Correct	883 ms	9924 KB	Output is correct
9	Correct	860 ms	10156 KB	Output is correct
10	Correct	806 ms	9968 KB	Output is correct
11	Correct	519 ms	9828 KB	Output is correct
12	Correct	818 ms	9924 KB	Output is correct
13	Correct	764 ms	9828 KB	Output is correct
14	Correct	617 ms	9840 KB	Output is correct
15	Correct	596 ms	9940 KB	Output is correct
16	Correct	556 ms	9916 KB	Output is correct
17	Correct	583 ms	9352 KB	Output is correct
18	Correct	592 ms	9456 KB	Output is correct
19	Correct	593 ms	9652 KB	Output is correct
20	Correct	592 ms	9344 KB	Output is correct
21	Correct	538 ms	9772 KB	Output is correct
22	Correct	718 ms	9916 KB	Output is correct
23	Correct	755 ms	9952 KB	Output is correct
24	Correct	715 ms	10052 KB	Output is correct
25	Correct	484 ms	9604 KB	Output is correct
26	Correct	504 ms	9672 KB	Output is correct
27	Correct	521 ms	9764 KB	Output is correct
28	Correct	489 ms	9684 KB	Output is correct
29	Correct	806 ms	9940 KB	Output is correct
30	Correct	820 ms	9756 KB	Output is correct
31	Correct	888 ms	9976 KB	Output is correct
32	Correct	859 ms	9848 KB	Output is correct
33	Correct	796 ms	9836 KB	Output is correct
34	Correct	628 ms	9776 KB	Output is correct
35	Correct	763 ms	9904 KB	Output is correct
36	Correct	817 ms	9844 KB	Output is correct