제출 #1157904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157904		alexdd	자리 배치 (IOI18_seats)	C++20	37 / 100	4094 ms	104064 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;

std::vector<int> x,y;
int H,W;

pair<pair<int,int>,pair<int,int>> aint[4000005];
pair<pair<int,int>,pair<int,int>> combine(pair<pair<int,int>,pair<int,int>> a, pair<pair<int,int>,pair<int,int>> b)
{
    return {{min(a.first.first,b.first.first),max(a.first.second,b.first.second)},{min(a.second.first,b.second.first),max(a.second.second,b.second.second)}};
}
pair<pair<int,int>,pair<int,int>> emp = {{INF,-INF},{INF,-INF}};
void upd(int nod, int st, int dr, int poz, pair<int,int> newv)
{
    if(st==dr)
    {
        aint[nod] = {{newv.first,newv.first},{newv.second,newv.second}};
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,newv);
    else upd(nod*2+1,mij+1,dr,poz,newv);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
pair<pair<int,int>,pair<int,int>> qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return emp;
    if(le==st && dr==ri)
        return aint[nod];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri)),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
pair<pair<int,int>,pair<int,int>> pref;
int cautare_binara(int nod, int st, int dr, pair<pair<int,int>,pair<int,int>> cur)
{
    if(st==dr)
    {
        if(combine(cur,aint[nod])==cur)
            return -1;
        pref = combine(pref, aint[nod]);
        return st;
    }
    int mij=(st+dr)/2;
    if(combine(aint[nod*2],cur) != cur)
        return cautare_binara(nod*2,st,mij,cur);
    else
    {
        pref = combine(pref, aint[nod*2]);
        return cautare_binara(nod*2+1,mij+1,dr,cur);
    }
}

bool verif(int i)
{
    pair<pair<int,int>,pair<int,int>> aux = qry(1,0,H*W-1,0,i);
    if((aux.first.second-aux.first.first+1) * (aux.second.second-aux.second.first+1) == i+1)
        return 1;
    return 0;
}

set<int> bune;
void calc(int a, int b)
{
    if(a>b)
        swap(a,b);

    auto it = bune.lower_bound(a);
    while(it != bune.end() && (*it) <= b)
        it = bune.erase(it);

    /*for(int i=a;i<=b;i++)
        if(verif(i))
            bune.insert(i);*/

    if(verif(a))
        bune.insert(a);
    if(verif(b))
        bune.insert(b);

    pair<pair<int,int>,pair<int,int>> prec = qry(1,0,H*W-1,0,a);
    while(1)
    {
        pref = emp;
        int cur = cautare_binara(1,0,H*W-1,prec);
        if(cur==-1 || cur-1 > b)
            break;
        if((prec.first.second-prec.first.first+1) * (prec.second.second-prec.second.first+1) == cur)
        {
            prec = pref;
            bune.insert(cur-1);
        }
        else
        {
            prec = pref;
            prec = qry(1,0,H*W-1,0,(prec.first.second-prec.first.first+1) * (prec.second.second-prec.second.first+1) - 1);
        }
    }
}
void give_initial_chart(int citH, int citW, std::vector<int> citR, std::vector<int> citC)
{
    H = citH;
    W = citW;
    x = citR;
    y = citC;
    for(int i=0;i<H*W;i++)
        upd(1,0,H*W-1,i,{x[i],y[i]});
    calc(0,H*W-1);
}
int swap_seats(int a, int b)
{
    if(H*W==1)
        return 1;

    swap(x[a],x[b]);
    swap(y[a],y[b]);
    upd(1,0,H*W-1,a,{x[a],y[a]});
    upd(1,0,H*W-1,b,{x[b],y[b]});

    calc(a,b);

    return bune.size();
}

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