Submission #294161

#	Time	Username	Problem	Language	Result	Execution time	Memory
294161		Kastanda	Seats (IOI18_seats)	C++11	37 / 100	4051 ms	211192 KiB

seats

// M
#include<bits/stdc++.h>
#include "seats.h"
#define pb push_back
using namespace std;
const int LG = 20;
struct RMQ
{
        vector < int > rmq[LG], mxq[LG], Log;
        inline void Init(vector < int > A)
        {
                rmq[0] = A;
                mxq[0] = A;
                int n = (int)A.size();
                for (int j = 1; j < LG && (1 << j) <= n; j ++)
                {
                        rmq[j] = mxq[j] = vector < int > (n);
                        for (int i = 0; i + (1 << j) <= n; i ++)
                        {
                                rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);
                                mxq[j][i] = max(mxq[j - 1][i], mxq[j - 1][i + (1 << (j - 1))]);
                        }
                }
                Log = vector < int > (n + 5, 0);
                for (int i = 2; i < n + 5; i ++)
                        Log[i] = Log[i >> 1] + 1;
        }
        inline int GetMin(int l, int r)
        {
                int lg = Log[r - l];
                return min(rmq[lg][l], rmq[lg][r - (1 << lg)]);
        }
        inline int GetMax(int l, int r)
        {
                int lg = Log[r - l];
                return max(mxq[lg][l], mxq[lg][r - (1 << lg)]);
        }

};
const int MXN = 1e6 + 10, N = 1009;
int n, m, R[MXN], C[MXN];
vector < vector < int > > A;
RMQ Row[N], Col[N];
inline void BuildRow(int r)
{
        vector < int > TMp;
        for (int j = 0; j < m; j ++)
                TMp.push_back(A[r][j]);
        Row[r].Init(TMp);
}
inline void BuildCol(int c)
{
        vector < int > TMp;
        for (int i = 0; i < n; i ++)
                TMp.push_back(A[i][c]);
        Col[c].Init(TMp);
}
inline int Calc()
{
        int Mx = 0, Cnt = 1;
        int lrow = R[0], rrow = R[0], lcol = C[0], rcol = C[0];

        while (true)
        {
                int mnl, mnr, mnu, mnd;
                mnl = mnr = mnu = mnd = INT_MAX;

                if (lrow > 0)
                        mnu = Row[lrow - 1].GetMin(lcol, rcol + 1);
                if (rrow + 1 < n)
                        mnd = Row[rrow + 1].GetMin(lcol, rcol + 1);
                if (lcol > 0)
                        mnl = Col[lcol - 1].GetMin(lrow, rrow + 1);
                if (rcol + 1 < m)
                        mnr = Col[rcol + 1].GetMin(lrow, rrow + 1);

                int mn = min({mnl, mnr, mnu, mnd});
                if (mn == INT_MAX)
                        break;

                if (mn == mnl)
                        lcol --, Mx = max(Mx, Col[lcol].GetMax(lrow, rrow + 1));
                else if (mn == mnr)
                        rcol ++, Mx = max(Mx, Col[rcol].GetMax(lrow, rrow + 1));
                else if (mn == mnu)
                        lrow --, Mx = max(Mx, Row[lrow].GetMax(lcol, rcol + 1));
                else if (mn == mnd)
                        rrow ++, Mx = max(Mx, Row[rrow].GetMax(lcol, rcol + 1));

                //printf("%d , %d :: %d , %d === %d :: %d\n", lrow, rrow, lcol, rcol, Mx, (rrow - lrow + 1) * (rcol - lcol + 1));

                if (Mx == (rrow - lrow + 1) * (rcol - lcol + 1) - 1)
                        Cnt ++;
        }
        return Cnt;
}

namespace Subtask4
{
        int mnl[MXN], mnr[MXN], mnu[MXN], mnd[MXN], CntRs;
        inline void Init()
        {
                CntRs = 1;
                mnl[0] = mnr[0] = C[0];
                mnu[0] = mnd[0] = R[0];
                for (int i = 1; i < n * m; i ++)
                {
                        mnl[i] = min(mnl[i - 1], C[i]);
                        mnr[i] = max(mnr[i - 1], C[i]);
                        mnu[i] = min(mnu[i - 1], R[i]);
                        mnd[i] = max(mnd[i - 1], R[i]);

                        if ((mnr[i] - mnl[i] + 1) * (mnd[i] - mnu[i] + 1) == i + 1)
                                CntRs ++;
                }
        }
        inline int Swap(int a, int b)
        {
                if (a > b)
                        swap(a, b);

                for (int i = a; i <= b; i ++)
                {
                        if ((mnr[i] - mnl[i] + 1) * (mnd[i] - mnu[i] + 1) == i + 1)
                                CntRs --;

                        mnl[i] = i ? mnl[i - 1] : INT_MAX;
                        mnr[i] = i ? mnr[i - 1] : INT_MIN;
                        mnu[i] = i ? mnu[i - 1] : INT_MAX;
                        mnd[i] = i ? mnd[i - 1] : INT_MIN;

                        mnl[i] = min(mnl[i], C[i]);
                        mnr[i] = max(mnr[i], C[i]);
                        mnu[i] = min(mnu[i], R[i]);
                        mnd[i] = max(mnd[i], R[i]);

                        if ((mnr[i] - mnl[i] + 1) * (mnd[i] - mnu[i] + 1) == i + 1)
                                CntRs ++;
                }
                return CntRs;
        }
}
int SUB4 = 0;
void give_initial_chart(int _H, int _W, vector < int > _R, vector < int > _C)
{
        n = _H; m = _W;
        for (int i = 0; i < n * m; i ++)
                R[i] = _R[i], C[i] = _C[i];

        for (int i = 0; i < n; i ++)
                A.pb(vector < int > (m, 0));
        for (int i = 0; i < n * m; i ++)
                A[R[i]][C[i]] = i;

        if (n > 1000 || m > 1000)
        {
                Subtask4::Init();
                SUB4 = 1;
                return ;
        }

        for (int i = 0; i < n; i ++)
                BuildRow(i);
        for (int j = 0; j < m; j ++)
                BuildCol(j);
}

int swap_seats(int a, int b)
{
        swap(R[a], R[b]);
        swap(C[a], C[b]);
        swap(A[R[a]][C[a]], A[R[b]][C[b]]);
        if (SUB4)
                return Subtask4::Swap(a, b);

        BuildRow(R[a]);
        BuildRow(R[b]);
        BuildCol(C[a]);
        BuildCol(C[b]);
        return Calc();
}

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