제출 #401068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401068		idk321	자리 배치 (IOI18_seats)	C++11	31 / 100	4075 ms	108056 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]);


    if (h * w <= 10000)
    {
        int res = 0;
        int hmin  = MA;
        int hmax = -1;
        int cmin = MA;
        int cmax = -1;
        for (int i = 0; i < h * w; i++)
        {
            hmin = min(hmin, r[i]);
            cmin = min(cmin, c[i]);
            hmax = max(hmax, r[i]);
            cmax = max(cmax, c[i]);
            if (i == (hmax - hmin + 1) * (cmax - cmin + 1) - 1) res++;
        }
        return res;
    }

    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])
        {
            int cur = ((byH[ch][2] + 1) * (byW[cw][2] + 1) - 1);
            if (cur >= byW[cw][0] && cur <= byW[cw][1] && cur >= byH[ch][0] && cur <= byH[ch][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

*/

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:160: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]
  160 |     while (ch < byH.size())
      |            ~~~^~~~~~~~~~~~
seats.cpp:162: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]
  162 |         while (cw < byW.size() && byW[cw][0] <= byH[ch][1])
      |                ~~~^~~~~~~~~~~~

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