Submission #114126

#	Time	Username	Problem	Language	Result	Execution time	Memory
114126		Alexa2001	Seats (IOI18_seats)	C++17	31 / 100	4075 ms	58872 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e6 + 5;

int N, M, n;
pair<int,int> where[Nmax];
int ans = 0, r1, c1, r2, c2, cnt, val;
int last_ans = -1;

#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)


class SegTree
{
    int mxR[Nmax<<2], mxC[Nmax<<2], mnR[Nmax<<2], mnC[Nmax<<2];

    void comb(int node, int x, int y)
    {
        mxR[node] = max(mxR[x], mxR[y]);
        mxC[node] = max(mxC[x], mxC[y]);
        mnR[node] = min(mnR[x], mnR[y]);
        mnC[node] = min(mnC[x], mnC[y]);
    }

    public:
        void init(int node, int st, int dr)
        {
            if(st == dr)
            {
                mxR[node] = mnR[node] = where[st].first;
                mxC[node] = mnC[node] = where[st].second;
                return;
            }

            init(left_son, st, mid);
            init(right_son, mid+1, dr);
            comb(node, left_son, right_son);
        }

        void update(int node, int st, int dr, int pos)
        {
            if(st == dr)
            {
                mxR[node] = mnR[node] = where[st].first;
                mxC[node] = mnC[node] = where[st].second;
                return;
            }

            if(pos <= mid) update(left_son, st, mid, pos);
                else update(right_son, mid+1, dr, pos);
            comb(node, left_son, right_son);
        }

        void query(int node, int st, int dr, int L, int R, int &r1, int &r2, int &c1, int &c2)
        {
            if(L <= st && dr <= R)
            {
                r1 = min(r1, mnR[node]);
                r2 = max(r2, mxR[node]);
                c1 = min(c1, mnC[node]);
                c2 = max(c2, mxC[node]);
                return;
            }

            if(L <= mid) query(left_son, st, mid, L, R, r1, r2, c1, c2);
            if(mid < R) query(right_son, mid+1, dr, L, R, r1, r2, c1, c2);
        }
} aint;

void enlarge(int x, int y)
{
    aint.query(1, 0, n-1, x, y, r1, r2, c1, c2);
}

int solve0(int x, int y)
{
    int i;
    int ans = last_ans;

    for(i=x; i<y; ++i)
    {
        r1 = c1 = n;
        r2 = c2 = 0;

        aint.query(1, 0, n-1, 0, i, r1, r2, c1, c2);
        if(i + 1 == (r2 - r1 + 1) * (c2 - c1 + 1)) --ans;
    }

    swap(where[x], where[y]);

    aint.update(1, 0, n-1, x);
    aint.update(1, 0, n-1, y);

    for(i=x; i<y; ++i)
    {
        r1 = c1 = n;
        r2 = c2 = 0;

        aint.query(1, 0, n-1, 0, i, r1, r2, c1, c2);
        if(i + 1 == (r2 - r1 + 1) * (c2 - c1 + 1)) ++ans;
    }

    last_ans = ans;
    return ans;
}

int swap_seats(int x, int y)
{
    if(x > y) swap(x, y);
    if(y - x <= 10000 && last_ans != -1) return solve0(x, y);

    swap(where[x], where[y]);

    aint.update(1, 0, n-1, x);
    aint.update(1, 0, n-1, y);

    ans = 0;
    val = 0;

    r1 = r2 = where[0].first;
    c1 = c2 = where[0].second;

    while(1)
    {
        if(val + 1 == (r2 - r1 + 1) * (c2 - c1 + 1))
        {
            ++ans;
            ++val;
            if(val == n)
            {
                last_ans = ans;
                return ans;
            }
            enlarge(val, val);
        }
        else
        {
            int cnt = (r2 - r1 + 1) * (c2 - c1 + 1);
            enlarge(val + 1, cnt - 1);
            val = cnt - 1;
        }
    }

    assert(0);
}


void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
    int i;
    n = H * W;
    N = H; M = W;

    for(i=0; i < N * M; ++i)
        where[i] = {R[i], C[i]};
    aint.init(1, 0, n-1);
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30