Submission #284392

#	Time	Username	Problem	Language	Result	Execution time	Memory
284392		MKopchev	Seats (IOI18_seats)	C++14	5 / 100	4080 ms	59768 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]);
}

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

    for(int i=0;i<H*W;i++)
        update(1,0,H*W-1,i);
}

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

    for(int i=0;i<n*m;i++)
    {
        info cur=query(1,0,n*m-1,i,i);
        //cout<<i<<" -> "<<cur.min_x<<" "<<cur.max_x<<" "<<cur.min_y<<" "<<cur.max_y<<endl;
    }

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

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

    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 'int eval()':
seats.cpp:87:14: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
   87 |         info cur=query(1,0,n*m-1,i,i);
      |              ^~~

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