Submission #738203

#	Time	Username	Problem	Language	Result	Execution time	Memory
738203		danikoynov	Seats (IOI18_seats)	C++14	25 / 100	4091 ms	253884 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;

struct seat
{
    int r, c;
};

seat s[maxn];
int h, w;
set < int > row[maxn], col[maxn];
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
    h = H;
    w = W;
    for (int i = 0; i < h * w; i ++)
    {
        s[i].r = R[i];
        s[i].c = C[i];
        row[R[i]].insert(i);
        col[C[i]].insert(i);
    }
}

struct event
{
    int val, type, tp;

    event(int _type = -1, int _val = -1, int _tp = -1)
    {
        type = _type;
        val = _val;
        tp = _tp;
    }
};

bool cmp(const event &e1, const event &e2)
{
    return e1.tp < e2.tp;
}
int swap_seats(int a, int b)
{
    row[s[a].r].erase(a);
    row[s[b].r].erase(b);
    col[s[a].c].erase(a);
    col[s[b].c].erase(b);
    swap(s[a], s[b]);
        row[s[a].r].insert(a);
    row[s[b].r].insert(b);
    col[s[a].c].insert(a);
    col[s[b].c].insert(b);

    vector < event > ev;

    vector < pair < int, int > > rx;
    for (int i = 0; i < h; i ++)
    {
        if (row[i].size() == 0)
            continue;
        rx.push_back({*row[i].begin(), i});
    }

    sort(rx.begin(), rx.end());
    ll max_row = -1e9, min_row = 1e9;
    for (int i = 0; i < rx.size(); i ++)
    {
        if (rx[i].second > max_row)
        {
            max_row = rx[i].second;
            ev.push_back(event(0, rx[i].second, rx[i].first));
        }
        if (rx[i].second < min_row)
        {
            min_row = rx[i].second;
            ev.push_back(event(1, rx[i].second, rx[i].first));
        }
    }

    vector < pair < int, int > > cx;
    for (int i = 0; i < w; i ++)
    {
        if (col[i].size() == 0)
            continue;;
        cx.push_back({*col[i].begin(), i});
    }

    sort(cx.begin(), cx.end());
    ll max_col = -1e9, min_col = 1e9;
    for (int i = 0; i < cx.size(); i ++)
    {
        if (cx[i].second > max_col)
        {
            max_col = cx[i].second;
            ev.push_back(event(2, cx[i].second, cx[i].first));
        }

        if (cx[i].second < min_col)
        {
            min_col = cx[i].second;
            ev.push_back(event(3, cx[i].second, cx[i].first));
        }
    }

    sort(ev.begin(), ev.end(), cmp);

    min_col = 1e9;
    max_col = -1e9;
    min_row = 1e9;
    max_row = -1e9;
    int ans = 1;
    for (int i = 0; i < ev.size(); i ++)
    {
        if (i != 0 && ev[i - 1].tp != ev[i].tp)
        {
            if ((max_row - min_row + 1) * (max_col - min_col + 1) ==
                ev[i].tp)
                    ans ++;
        }
        if (ev[i].type == 0)
        {
            max_row = ev[i].val;
        }
        else
        if (ev[i].type == 1)
        {
            min_row = ev[i].val;
        }
        else
        if (ev[i].type == 2)
        {
            max_col = ev[i].val;
        }
        else
        if (ev[i].type == 3)
        {
            min_col = ev[i].val;
        }
    }
    return ans;
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < rx.size(); i ++)
      |                     ~~^~~~~~~~~~~
seats.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < cx.size(); i ++)
      |                     ~~^~~~~~~~~~~
seats.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int i = 0; i < ev.size(); i ++)
      |                     ~~^~~~~~~~~~~

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