Submission #719769

#	Time	Username	Problem	Language	Result	Execution time	Memory
719769		bin9638	Seats (IOI18_seats)	C++17	0 / 100	467 ms	98748 KiB

seats

#include <bits/stdc++.h>

#ifndef SKY
#include "seats.h"
#endif // SKY

using namespace std;

#define N 1000010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int n,m,ans;
ii pos[N];

int vet()
{
    int top=pos[0].fs,bot=pos[0].fs,lef=pos[0].sc,righ=pos[0].sc,res=1;
    for(int i=1;i<n*m;i++)
    {
        top=min(top,pos[i].fs);
        bot=max(bot,pos[i].fs);
        lef=min(lef,pos[i].sc);
        righ=max(righ,pos[i].sc);
        if((bot-top+1)*(righ-lef+1)==i+1)
                res++;
    }
    return res;
}

struct haha
{
    int lef,righ,top,bot;
};

haha get_max(haha A,haha B)
{
    return{min(A.lef,B.lef),max(A.righ,B.righ),min(A.top,B.top),max(A.bot,B.bot)};
};

struct IT
{
    haha ST[N*4];

    void update(int id,int l,int r,int i,ii val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
            ST[id]={val.sc,val.sc,val.fs,val.fs};
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        ST[id]=get_max(ST[id*2],ST[id*2+1]);
    }

    haha get(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
           return{100000000,-100000000,100000000,-100000000};
        if(l>=u&&r<=v)
            return ST[id];
        int mid=(l+r)/2;
        return get_max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
}T;

int solve(int l,int r)
{
    haha val=T.get(1,1,n*m,1,l+1);
    int res=0,vt=l;
    while(vt<=r)
    {
        if(vt+1==(val.righ-val.lef+1)*(val.bot-val.top+1))
            res++;
        int them=max(1,(val.righ-val.lef+1)*(val.bot-val.top+1)-(vt+1));
        val=T.get(1,1,n*m,1,vt+them+1);
        vt+=them;
    }
    return res;
}

int swap_seats(int a, int b)
{
    if(a>b)
        swap(a,b);
    ans-=solve(a,b-1);
    swap(pos[a],pos[b]);
    ans+=solve(a,b-1);
}


void give_initial_chart(int NNN, int MMM, std::vector<int> R, std::vector<int> C)
{
    n=NNN;
    m=MMM;
    for(int i=0;i<n*m;i++)
        pos[i]={R[i],C[i]};
    ans=vet();
    for(int i=0;i<n*m;i++)
        T.update(1,1,n*m,i+1,pos[i]);
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}
#endif

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:96:1: warning: no return statement in function returning non-void [-Wreturn-type]
   96 | }
      | ^

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