Submission #868072

#	Time	Username	Problem	Language	Result	Execution time	Memory
868072		sleepntsheep	Segments (IZhO18_segments)	C++17	0 / 100	103 ms	17488 KiB

segments

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 200005
#define B 450

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

int compare_length_descending(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_descending);
    for (int i = 0; i < na; ++i)
    {
        e[i/B][sz[i/B]] = f[i/B][sz[i/B]] = i, ++sz[i/B];
    }
    for (int i = 0; i <= (na / B); ++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] - 1; j >= 0; --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);

    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 == 5000) rebuild();
            ++S;
        }
        else if (op == 2)
        {
            struct line del = o[x];
            del.w = -1;
            c[nc++] = del;
            if (nc == 5000) 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/B, sb = zb+1;
                    for (struct line *j = a + Z; j < a + sb * B; ++j) if (j->r - l + 1 < k || r - j->l + 1 < k) z -= j->w;
                    for (int j = sb; j * sb <= na; ++j)
                    {
                        /* r - j->l + 1 < k === j->l > r - k + 1 */
                        int cnt = 0;
                        for (int L = 0, R = sz[j]; 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]; 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;

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

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d%d", &n, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d%d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |             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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25