Submission #868108

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
868108	2023-10-30T12:40:56 Z	sleepntsheep	Segments (IZhO18_segments)	C++17	16 / 100	962 ms	9868 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
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[N], pf[N];

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];
    pf[0] = a[0].w;
    for (int i = 1; i < na; ++i) pf[i] = pf[i-1] + a[i].w;
    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)
                {
                    if (Z)
                        z -= pf[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:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d%d", &n, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d%d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |             scanf("%d", &y);
      |             ~~~~~^~~~~~~~~~
segments.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |             scanf("%d%d", &y, &k); z=0;
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	543 ms	9212 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	508 ms	9656 KB	Output is correct
2	Correct	521 ms	9364 KB	Output is correct
3	Correct	495 ms	9444 KB	Output is correct
4	Correct	517 ms	9416 KB	Output is correct
5	Correct	739 ms	9404 KB	Output is correct
6	Correct	713 ms	9272 KB	Output is correct
7	Correct	710 ms	9352 KB	Output is correct
8	Correct	869 ms	9612 KB	Output is correct
9	Correct	962 ms	9652 KB	Output is correct
10	Correct	814 ms	9868 KB	Output is correct
11	Correct	581 ms	9476 KB	Output is correct
12	Correct	860 ms	9624 KB	Output is correct
13	Correct	815 ms	9524 KB	Output is correct
14	Correct	648 ms	9552 KB	Output is correct
15	Correct	618 ms	9552 KB	Output is correct
16	Correct	564 ms	9504 KB	Output is correct
17	Correct	601 ms	9168 KB	Output is correct
18	Correct	653 ms	9392 KB	Output is correct
19	Correct	613 ms	9336 KB	Output is correct
20	Correct	591 ms	9160 KB	Output is correct
21	Correct	546 ms	9468 KB	Output is correct
22	Correct	739 ms	9480 KB	Output is correct
23	Correct	800 ms	9452 KB	Output is correct
24	Correct	724 ms	9552 KB	Output is correct
25	Correct	490 ms	9444 KB	Output is correct
26	Correct	488 ms	9428 KB	Output is correct
27	Correct	493 ms	9448 KB	Output is correct
28	Correct	492 ms	9412 KB	Output is correct
29	Correct	793 ms	9528 KB	Output is correct
30	Correct	802 ms	9540 KB	Output is correct
31	Correct	854 ms	9592 KB	Output is correct
32	Correct	811 ms	9632 KB	Output is correct
33	Correct	771 ms	9508 KB	Output is correct
34	Correct	603 ms	9536 KB	Output is correct
35	Correct	757 ms	9508 KB	Output is correct
36	Correct	789 ms	9616 KB	Output is correct