Submission #284397

#	Time	Username	Problem	Language	Result	Execution time	Memory
284397		MKopchev	Seats (IOI18_seats)	C++14	0 / 100	4099 ms	57228 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e6+42;

int n,m;

struct info
{
    int min_x,min_y,max_x,max_y;
};

info tree[4*nmax];

pair<int,int> where[nmax];

info my_merge(info a,info b)
{
    info ret;

    ret.min_x=min(a.min_x,b.min_x);
    ret.max_x=max(a.max_x,b.max_x);

    ret.min_y=min(a.min_y,b.min_y);
    ret.max_y=max(a.max_y,b.max_y);

    return ret;
}
void update(int node,int l,int r,int pos)
{
    if(l==r)
    {
        tree[node].min_x=where[pos].first;
        tree[node].max_x=where[pos].first;

        tree[node].min_y=where[pos].second;
        tree[node].max_y=where[pos].second;

        return;
    }
    int av=(l+r)/2;

    if(pos<=av)update(node*2,l,av,pos);
    else update(node*2+1,av+1,r,pos);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node].min_x=where[l].first;
        tree[node].max_x=where[l].first;

        tree[node].min_y=where[l].second;
        tree[node].max_y=where[l].second;

        return;
    }
    int av=(l+r)/2;

    build(node*2,l,av);
    build(node*2+1,av+1,r);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}


info query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree[node];

    int av=(l+r)/2;

    info ret;
    ret.min_x=1e9;
    ret.max_x=0;
    ret.min_y=1e9;
    ret.max_y=0;

    if(lq<=av)ret=my_merge(ret,query(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ret=my_merge(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));

    return ret;
}


void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    n=H;
    m=W;

    for(int i=0;i<H*W;i++)
    {
        where[i]={R[i],C[i]};
    }

    build(1,0,n*m-1);
}

int eval()
{
    int ret=0,i=0;

    info cur;

    cur.min_x=where[0].first;
    cur.max_x=where[0].first;

    cur.min_y=where[0].second;
    cur.max_y=where[0].second;

    while(i<n*m)
    {
        int area=(cur.max_x-cur.min_x+1)*(cur.max_y-cur.min_y+1);

        if(area==i+1)
        {
            ret++;
            i++;

            cur.min_x=min(cur.min_x,where[i].first);
            cur.max_x=max(cur.max_x,where[i].first);

            cur.min_y=min(cur.min_y,where[i].second);
            cur.max_y=max(cur.max_y,where[i].second);
        }

        else
        {
            cur=my_merge(cur,query(1,0,n*m-1,i+1,area-1));

            area=(cur.max_x-cur.min_x+1)*(cur.max_y-cur.min_y+1);

            i=max(i+1,area-1);
        }
    }

    return ret;
}

int swap_seats(int a, int b)
{
    swap(where[a],where[b]);

    update(1,0,n*m-1,a);
    update(1,0,n*m-1,b);

    return eval();
}

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