Submission #156914

#	Time	Username	Problem	Language	Result	Execution time	Memory
156914		Alexa2001	Seats (IOI18_seats)	C++17	100 / 100	2210 ms	222096 KiB

seats

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

using namespace std;

const int Nmax = 1e6 + 5;
const int inf = 1e9;

typedef long long ll;
typedef pair<int,int> Pair;


ll mars[Nmax];
int N, M, P;
int posL[Nmax], posC[Nmax];

vector< vector<int> > matrix;
vector< vector< pair<Pair, Pair> > > coef;




///////////////////////////////////////////////////
struct info
{
    ll mn; int cnt;
};

info operator + (info a, info b)
{
    if(a.mn < b.mn) return a;
    if(b.mn < a.mn) return b;
    return {a.mn, a.cnt + b.cnt};
}

void operator += (info &a, ll b)
{
    a.mn += b;
}
//////////////////////////////////////////////////


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

class SegTree
{
    info a[Nmax<<2];
    ll lazy[Nmax<<2];

    void propag(int node)
    {
        if(!lazy[node]) return;

        lazy[left_son] += lazy[node];
        lazy[right_son] += lazy[node];

        a[left_son] += lazy[node];
        a[right_son] += lazy[node];

        lazy[node] = 0;
    }

public:
    void build(int node, int st, int dr, ll A[])
    {
        lazy[node] = 0;
        if(st == dr)
        {
            a[node] = {A[st], 1};
            return;
        }

        build(left_son, st, mid, A);
        build(right_son, mid+1, dr, A);

        a[node] = a[left_son] + a[right_son];
    }

    void update(int node, int st, int dr, int L, int R, int add)
    {
        if(L > R) return;
        if(L <= st && dr <= R)
        {
            lazy[node] += add;
            a[node] += add;
            return;
        }

        propag(node);

        if(L <= mid) update(left_son, st, mid, L, R, add);
        if(mid < R) update(right_son, mid+1, dr, L, R, add);

        a[node] = a[left_son] + a[right_son];
    }

    info query()
    {
        return a[1];
    }
} aint;

pair<Pair, Pair> get_coef(int x, int y)
{
    vector<int> aux;
    aux.push_back(matrix[x][y]);
    aux.push_back(matrix[x+1][y]);
    aux.push_back(matrix[x][y+1]);
    aux.push_back(matrix[x+1][y+1]);

    sort(aux.begin(), aux.end());

    return { {aux[0], aux[1] - 1}, {aux[2], aux[3] - 1} };
}

void add_mars(Pair a, int c)
{
    mars[a.first] += c; mars[a.second+1] -= c;
}

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

    int i, j;

    matrix.resize(N+2);
    for(auto &it : matrix) it.resize(M+2, 0);

    coef.resize(N+1);
    for(auto &it : coef) it.resize(M+1);


    for(i=0; i<=N+1; ++i)
        for(j=0; j<=M+1; ++j)
            matrix[i][j] = ( (1 <= i && i <= N && 1 <= j && j <= M) ? 0 : P);

    for(i=0; i<P; ++i)
    {
        ++R[i]; ++C[i];
        posL[i] = R[i], posC[i] = C[i];
        matrix[R[i]][C[i]] = i;
    }

    for(i=0; i<=N; ++i)
        for(j=0; j<=M; ++j) /// ce coeficient are patratul cu coltul stanga-sus in (i,j) ?
            coef[i][j] = get_coef(i, j);

    for(i=0; i<=P; ++i) mars[i] = 0;

    for(i=0; i<=N; ++i)
        for(j=0; j<=M; ++j)
        {
            add_mars(coef[i][j].first, 1);
            add_mars(coef[i][j].second, inf);
        }

    for(i=1; i<P; ++i)
        mars[i] += mars[i-1];

    aint.build(1, 0, P-1, mars);
}

int swap_seats(int id1, int id2)
{
    int l1, c1, l2, c2;

    l1 = posL[id1]; c1 = posC[id1];
    l2 = posL[id2]; c2 = posC[id2];

    vector<Pair> changes;

    changes.push_back({l1, c1});
    changes.push_back({l1-1, c1});
    changes.push_back({l1, c1-1});
    changes.push_back({l1-1, c1-1});

    changes.push_back({l2, c2});
    changes.push_back({l2-1, c2});
    changes.push_back({l2, c2-1});
    changes.push_back({l2-1, c2-1});

    sort(changes.begin(), changes.end());
    changes.erase( unique(changes.begin(), changes.end()), changes.end() );

    swap(posL[id1], posL[id2]);
    swap(posC[id1], posC[id2]);
    swap(matrix[l1][c1], matrix[l2][c2]);

    for(auto it : changes)
    {
        int pc, pl;
        tie(pl, pc) = it;

        auto C = coef[pl][pc];

        aint.update(1, 0, P-1, C.first.first, C.first.second, -1);
        aint.update(1, 0, P-1, C.second.first, C.second.second, -inf);

        C = coef[pl][pc] = get_coef(pl, pc);

        aint.update(1, 0, P-1, C.first.first, C.first.second, +1);
        aint.update(1, 0, P-1, C.second.first, C.second.second, +inf);
    }

    auto res = aint.query();
    assert(res.mn == 4);
    return res.cnt;
}

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