Submission #80812

#	Time	Username	Problem	Language	Result	Execution time	Memory
80812		Bodo171	Seats (IOI18_seats)	C++14	100 / 100	3232 ms	233352 KiB

seats

#include "seats.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int nmax=1000*1000+5;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
struct node
{
    int mn,upd,cnt;
}arb[4*nmax];
vector<int> a[nmax],viz[nmax];
vector<int> r,c;
int v[10],L[15],C[15];
int st,dr,n,h,w,lf,cf,i,j,nr;
void update(int nod,int l,int r,int st,int dr,int value)
{
    if(st<=l&&r<=dr)
    {
        arb[nod].upd+=value;
        return;
    }
    int m=(l+r)/2;
    if(arb[nod].upd)
    {
        update(2*nod,l,m,l,m,arb[nod].upd);
        update(2*nod+1,m+1,r,m+1,r,arb[nod].upd);
        arb[nod].upd=0;
    }
    if(st<=m) update(2*nod,l,m,st,dr,value);
    if(m<dr) update(2*nod+1,m+1,r,st,dr,value);
    arb[nod].mn=min(arb[2*nod].mn+arb[2*nod].upd,arb[2*nod+1].mn+arb[2*nod+1].upd);
    arb[nod].cnt=0;
    if(arb[nod].mn==arb[2*nod].mn+arb[2*nod].upd)
        arb[nod].cnt+=arb[2*nod].cnt;
    if(arb[nod].mn==arb[2*nod+1].mn+arb[2*nod+1].upd)
        arb[nod].cnt+=arb[2*nod+1].cnt;
}
void build(int nod,int l,int r)
{
    if(l==r)
    {
        arb[nod].cnt=1;
        return;
    }
    int m=(l+r)/2;
    build(2*nod,l,m);
    build(2*nod+1,m+1,r);
    arb[nod].cnt=arb[2*nod].cnt+arb[2*nod+1].cnt;
}
void upd(int l,int c,int cat)
{
    st=a[l][c];dr=min(a[l-1][c],a[l][c-1])-1;//facem update pt colt
    if(st<=dr)
        update(1,1,n,st,dr,cat);
    //facem update pt celule din afara
    for(int idx=0;idx<4;idx++)
    {
        lf=l+d1[idx];cf=c+d2[idx];
        v[idx]=a[lf][cf];
    }
    sort(v,v+4);
    st=v[1];dr=a[l][c]-1;
    if(st<=dr)
        update(1,1,n,st,dr,cat);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  r=R;c=C;
  for(i=0;i<=H+1;i++)
    for(j=1;j<=W+3;j++)
         a[i].push_back(n+1),viz[i].push_back(0);
  for(i=0;i<r.size();i++)
  {
      r[i]++;c[i]++;
      a[r[i]][c[i]]=i+1;
  }
  h=H,w=W;
  n=h*w;
  build(1,1,n);
  for(i=0;i<=h+1;i++)
      a[i][0]=a[i][w+1]=n+1;
  for(i=0;i<=w+1;i++)
    a[0][i]=a[h+1][i]=n+1;
  for(i=1;i<=h;i++)
    for(j=1;j<=w;j++)
  {
      upd(i,j,1);
  }
}
void rupe_tot(int ll,int cc)
{
    if(!viz[ll][cc])
    {
        viz[ll][cc]=1;
        ++nr;
        L[nr]=ll;C[nr]=cc;
    }
    for(int idx=0;idx<4;idx++)
    {
        lf=ll+d1[idx];cf=cc+d2[idx];
        if((!viz[lf][cf])&&lf>=1&&cf>=1&&lf<=h&&cf<=w)
        {
            viz[lf][cf]=1;
            ++nr;
            L[nr]=lf;C[nr]=cf;
        }
    }
}
int swap_seats(int aa, int b) {
   nr=0;
   rupe_tot(r[aa],c[aa]);
   rupe_tot(r[b],c[b]);
   for(int i=1;i<=nr;i++)
    upd(L[i],C[i],-1);
   swap(a[r[aa]][c[aa]],a[r[b]][c[b]]);
   swap(r[aa],r[b]);swap(c[aa],c[b]);
   for(int i=1;i<=nr;i++)
    upd(L[i],C[i],1),viz[L[i]][C[i]]=0;
   if(arb[1].mn+arb[1].upd==1) return arb[1].cnt;
   return 0;
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:73:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<r.size();i++)
           ~^~~~~~~~~

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