Submission #294202

#	Time	Username	Problem	Language	Result	Execution time	Memory
294202		Kastanda	Seats (IOI18_seats)	C++11	100 / 100	2380 ms	99544 KiB

seats

// M
#include<bits/stdc++.h>
#include "seats.h"
#define pb push_back
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int MXN = 1e6 + 10;
int n, m, k, R[MXN], C[MXN], PS[MXN];
int MN[MXN * 4], LZ[MXN * 4], Cnt[MXN * 4];
vector < vector < int > > A;
void Build(int id = 1, int l = 0, int r = k)
{
        if (r - l < 2)
        {
                Cnt[id] = 1;
                MN[id] = PS[l];
                return ;
        }
        Build(lc, l, md);
        Build(rc, md, r);
        MN[id] = min(MN[lc], MN[rc]);
        Cnt[id] = 0;
        if (MN[id] == MN[lc]) Cnt[id] += Cnt[lc];
        if (MN[id] == MN[rc]) Cnt[id] += Cnt[rc];
}
inline void Shift(int id)
{
        MN[lc] += LZ[id];
        MN[rc] += LZ[id];
        LZ[lc] += LZ[id];
        LZ[rc] += LZ[id];
        LZ[id] = 0;
}
int le, ri, val;
void Add(int id = 1, int l = 0, int r = k)
{
        if (ri <= l || r <= le)
                return ;
        if (le <= l && r <= ri)
        {
                MN[id] += val;
                LZ[id] += val;
                return ;
        }
        Shift(id);
        Add(lc, l, md);
        Add(rc, md, r);
        MN[id] = min(MN[lc], MN[rc]);
        Cnt[id] = 0;
        if (MN[id] == MN[lc]) Cnt[id] += Cnt[lc];
        if (MN[id] == MN[rc]) Cnt[id] += Cnt[rc];
}
inline void Do(int i, int j, int _val)
{
        vector < int > tmp = {A[i][j], A[i + 1][j], A[i][j + 1], A[i + 1][j + 1]};
        sort(tmp.begin(), tmp.end());
        le = tmp[0]; ri = tmp[1]; val = _val;
        Add();
        le = tmp[2]; ri = tmp[3]; val = _val;
        Add();
}
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];

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

        for (int i = 0; i <= n; i ++)
                for (int j = 0; j <= m; j ++)
                {
                        vector < int > tmp = {A[i][j], A[i + 1][j], A[i][j + 1], A[i + 1][j + 1]};
                        sort(tmp.begin(), tmp.end());
                        PS[tmp[0]] ++; PS[tmp[1]] --;
                        PS[tmp[2]] ++; PS[tmp[3]] --;
                }
        for (int i = 1; i < k; i ++)
                PS[i] += PS[i - 1];
        Build();
}

int swap_seats(int a, int b)
{
        vector < pair < int , int > > vec;
        for (int dx = -1; dx <= 0; dx ++)
                for (int dy = -1; dy <= 0; dy ++)
                        vec.push_back({R[a] + dx, C[a] + dy}), vec.push_back({R[b] + dx, C[b] + dy});
        sort(vec.begin(), vec.end());
        vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
        for (auto X : vec)
                Do(X.first, X.second, -1);

        swap(R[a], R[b]);
        swap(C[a], C[b]);
        swap(A[R[a]][C[a]], A[R[b]][C[b]]);

        for (auto X : vec)
                Do(X.first, X.second, 1);

        assert(MN[1] == 4);

        return Cnt[1];
}

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