Submission #401059

#	Time	Username	Problem	Language	Result	Execution time	Memory
401059		idk321	Seats (IOI18_seats)	C++11	5 / 100	4089 ms	72644 KiB

seats

#include "seats.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

std::vector<int> r;
vector<int> c;
int h, w;
const int N = 1000000;
int tree[4 * N][2][2];
const int MA = 2000000000;

void ins(int num, int i, int a, int b, int node, int typ)
{
    if (a == b)
    {

        tree[node][typ][0] = num;
        tree[node][typ][1] = num;
        return;
    }


    int mid = (a + b) / 2;
    if (i <= mid) ins(num, i, a, mid, node * 2, typ);
    if (i > mid) ins(num, i, mid + 1, b, node * 2 + 1, typ);

    tree[node][typ][0] = min(tree[node * 2][typ][0], tree[node * 2 + 1][typ][0]);
    tree[node][typ][1] = max(tree[node * 2][typ][1], tree[node * 2 + 1][typ][1]);
}

int firstWith(int diff, int a, int b, int cmin, int cmax, int node, int typ)
{

    if (a == b)
    {
        if (abs(max(cmax, tree[node][typ][1]) - min(cmin, tree[node][typ][0])) == diff) return a;
        else return -1;
    }


    int mid = (a + b) / 2;
    if (abs(max(cmax, tree[node * 2][typ][1]) - min(cmin, tree[node * 2][typ][0])) >= diff) return firstWith(diff, a, mid, cmin, cmax, node * 2, typ);
    cmin = min(cmin, tree[node * 2][typ][0]);
    cmax = max(cmax, tree[node * 2][typ][1]);
    return firstWith(diff, mid + 1, b, cmin, cmax, node * 2+  1, typ);
}

void getDiff(int to, int a, int b, int& cmin, int& cmax, int node, int typ)
{
    if (to >= b)
    {
        cmin = min(tree[node][typ][0], cmin);
        cmax = max(cmax, tree[node][typ][1]);
        return;
    }

    int mid = (a + b) / 2;
    getDiff(to, a, mid, cmin, cmax, node * 2, typ);
    if (to > mid) getDiff(to, mid + 1, b, cmin, cmax, node * 2 + 1, typ);
}


void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  r = R;
  c = C;
  h = H;
  w = W;
    for (int i = 0;  i< h * w; i++)
    {
        ins(r[i], i, 0, h * w - 1, 1, 0);
    }
    for (int i = 0;  i< h * w; i++)
    {
        ins(c[i], i, 0, h * w - 1, 1, 1);
    }
}

bool isGood(int i)
{

    int amin = MA;
    int amax = -1;
    getDiff(i, 0, h * w - 1, amin, amax, 1, 0);
    int a = abs(amax - amin + 1);
    int bmin = MA;
    int bmax = -1;
    getDiff(i, 0, h * w - 1, bmin, bmax, 1, 1);
    int b = abs(bmax - bmin + 1);

    return (i + 1) == a * b;
}

int swap_seats(int a, int b) {

    swap(r[a], r[b]);
    swap(c[a], c[b]);

    ins(r[a], a, 0, h * w - 1, 1, 0);
    ins(c[a], a, 0, h * w - 1, 1, 1);
    ins(r[b], b, 0, h * w - 1, 1, 0);
    ins(c[b], b, 0, h * w - 1, 1, 1);



    vector<array<int, 3>> byH;
    vector<array<int, 3>> byW;
    int last = 0;
    int cval = 0;
    for (int i = 1; i < h; i++)
    {
        int nxt = firstWith(i, 0, h * w - 1, MA, -1, 1, 0);
        if (nxt != -1)
        {
            byH.push_back({last, nxt - 1, cval});
            cval = i;
            last = nxt;
        }
    }
    byH.push_back({last, h * w - 1, cval});
    last = 0;
    cval = 0;
    for (int i = 1; i < w; i++)
    {
        int nxt = firstWith(i, 0, h * w - 1, MA, -1, 1, 1);
        if (nxt != -1)
        {
            byW.push_back({last, nxt - 1, cval});
            last = nxt;
            cval = i;
        }

    }
    byW.push_back({last, h * w - 1, cval});



    int ch = 0;
    int cw = 0;
    set<int> good;
    while (ch < byH.size())
    {
        while (cw < byW.size() && byW[cw][0] <= byH[ch][1])
        {
            if (isGood((byH[ch][2] + 1) * (byW[cw][2] + 1) - 1)) good.insert((byH[ch][2] + 1) * (byW[cw][2] + 1) - 1);
            if (byW[cw][1] > byH[ch][1]) break;
            cw++;
        }

        ch++;
    }

    return good.size();
}

/*
1 5 1
0 0
0 1
0 2
0 3
0 4
0 4

*/

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:142:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     while (ch < byH.size())
      |            ~~~^~~~~~~~~~~~
seats.cpp:144:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         while (cw < byW.size() && byW[cw][0] <= byH[ch][1])
      |                ~~~^~~~~~~~~~~~

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