Submission #1157863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157863		alexdd	Seats (IOI18_seats)	C++20	0 / 100	366 ms	56740 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));
}
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;
        return st;
    }
    int mij=(st+dr)/2;
    if(combine(aint[nod*2],cur) != cur)
        return cautare_binara(nod*2,st,mij,cur);
    else
        return cautare_binara(nod*2+1,mij+1,dr,cur);
}


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]});
}

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;
}
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]});

    int cur=0,cnt=2;
    while(1)
    {
        cur = cautare_binara(1,0,H*W-1,qry(1,0,H*W-1,0,cur));
        if(cur==-1)
            break;
        if(verif(cur-1))
            cnt++;
    }
    return cnt;
}

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