Submission #294181

#	Time	Username	Problem	Language	Result	Execution time	Memory
294181		Kastanda	Seats (IOI18_seats)	C++11	33 / 100	2191 ms	62200 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, N = 1009;
int n, m, R[MXN], C[MXN], B[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 = m)
{
        Cnt[id] = r - l;
        if (r - l < 2)
                return ;
        Build(lc, l, md);
        Build(rc, md, r);
}
inline void Shift(int id)
{
        MN[lc] += LZ[id];
        MN[rc] += LZ[id];
        LZ[lc] += LZ[id];
        LZ[rc] += LZ[id];
        LZ[id] = 0;
}
void Add(int le, int ri, int val, int id = 1, int l = 0, int r = m)
{
        if (ri <= l || r <= le)
                return ;
        if (le <= l && r <= ri)
        {
                MN[id] += val;
                LZ[id] += val;
                return ;
        }
        Shift(id);
        Add(le, ri, val, lc, l, md);
        Add(le, ri, val, 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 val)
{
        //printf("%d : %d ::: %d\n", min(B[i], B[i + 1]), max(B[i], B[i + 1]), val);
        Add(min(B[i], B[i + 1]), max(B[i], B[i + 1]), val);
}
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;

        assert(n == 1);
        for (int i = 0; i < m; i ++)
                B[C[i] + 1] = i;
        Build();
        B[0] = B[m + 1] = m + 1;
        for (int i = 0; i <= m; i ++)
                Do(i, 1);
}

int swap_seats(int a, int b)
{
        swap(R[a], R[b]);
        swap(C[a], C[b]);

        int c = C[a] + 1;
        int d = C[b] + 1;

        if (c > d)
                swap(c, d);

        Do(c - 1, -1);
        Do(c, -1);
        if (d - 1 > c)
                Do(d - 1, -1);
        Do(d, -1);

        swap(B[c], B[d]);
        Do(c - 1, 1);
        Do(c, 1);
        if (d - 1 > c)
                Do(d - 1, 1);
        Do(d, 1);

        return Cnt[1];
}

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