Submission #284402

#	Time	Username	Problem	Language	Result	Execution time	Memory
284402		MKopchev	Seats (IOI18_seats)	C++14	25 / 100	4096 ms	72824 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)
{
    a.min_x=min(a.min_x,b.min_x);
    a.max_x=max(a.max_x,b.max_x);

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

    return a;
}
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(rq<=av)return query(node*2,l,av,lq,rq);
    if(av<lq)return query(node*2+1,av+1,r,lq,rq);

    return my_merge(query(node*2,l,av,lq,av),query(node*2+1,av+1,r,av+1,rq));
}


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;

    int in=0;

    while(i<n*m)
    {
        info cur=query(1,0,n*m-1,0,i);

        in++;

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

        //cout<<i<<" -> "<<area<<" "<<cur.min_x<<" "<<cur.max_x<<" "<<cur.min_y<<" "<<cur.max_y<<endl;

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

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

    //cout<<"in= "<<in<<endl;

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

Compilation message (stderr)

seats.cpp: In function 'info query(int, int, int, int, int)':
seats.cpp:75:10: warning: variable 'ret' set but not used [-Wunused-but-set-variable]
   75 |     info ret;
      |          ^~~

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