Submission #1042053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042053		vnm06	Seats (IOI18_seats)	C++14	100 / 100	2080 ms	121172 KiB

seats

#include<bits/stdc++.h>
#include "seats.h"

using namespace std;

int h, w;
int lazy[4000005];
int segm[2][4000005];

void push_lazy(int v, int le, int ri)
{
  segm[0][v]+=lazy[v];
  if(le!=ri)
  {
    lazy[2*v]+=lazy[v];
    lazy[2*v+1]+=lazy[v];
  }
  lazy[v]=0;
}

void update(int v, int le, int ri, int be, int en, int st)
{
  if(segm[1][v]==0) segm[1][v]=ri-le+1;
  push_lazy(v, le, ri);
  //if(v==1) cout<<be<<" "<<en<<" "<<st<<endl;
  if(le>en || ri<be) return;
  if(be<=le && ri<=en)
  {
    segm[0][v]+=st;
    if(le!=ri) {lazy[2*v]+=st; lazy[2*v+1]+=st;}
    return;
  }
  int mid=(le+ri)/2;
  update(2*v, le, mid, be, en, st);
  update(2*v+1, mid+1, ri, be, en, st);
  if(segm[0][2*v]<segm[0][2*v+1])
  {
    segm[0][v]=segm[0][2*v];
    segm[1][v]=segm[1][2*v];
  }
  else if(segm[0][2*v]>segm[0][2*v+1])
  {
    segm[0][v]=segm[0][2*v+1];
    segm[1][v]=segm[1][2*v+1];
  }
  else
  {
    segm[0][v]=segm[0][2*v+1];
    segm[1][v]=segm[1][2*v]+segm[1][2*v+1];
  }
}

int query(int v, int le, int ri, int be, int en, int val)
{
  push_lazy(v, le, ri);
  if(le>en || ri<be) return 0;
  if(be<=le && ri<=en)
  {
    if(segm[0][v]==val) return segm[1][v];
    return 0;
  }
  int mid=(le+ri)/2;
  return query(2*v, le, mid, be, en, val) + query(2*v+1, mid+1, ri, be, en, val);
}

vector<vector<int> > tabl;
std::vector<int> rows, cols;

void upd_rect(int r, int c, int st)
{
      int val[4];
      val[0]=tabl[r][c];
      val[1]=tabl[r+1][c];
      val[2]=tabl[r][c+1];
      val[3]=tabl[r+1][c+1];
      sort(val, val+4);
      if(val[1]==10000000) update(1, 0, h*w-1, val[0], h*w-1, st);
      else update(1, 0, h*w-1, val[0], val[1]-1, st);
      if(val[3]!=10000000) update(1, 0, h*w-1, val[2], val[3]-1, st);

}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) 
{
  h=H;
  w=W;
  rows=R;
  cols=C;
  tabl.resize(H+2);
  for(int i=0; i<H+2; i++) 
  {
    tabl[i].resize(W+2);
    for(int j=0; j<W+2; j++) tabl[i][j]=1e7;
  }
  for(int i=0; i<H*W; i++) tabl[R[i]+1][C[i]+1]=i;
  for(int r=0; r<=H; r++)
  {
    for(int c=0; c<=W; c++)
    {
      upd_rect(r, c, 1);
    }
  }
  //for(int j=1; j<=13; j++) //cout<<segm[0][j]<<" "<<segm[1][j]<<endl;
}

int swap_seats(int a, int b) 
{
  int r1=rows[a], r2=rows[b], c1=cols[a], c2=cols[b];
  r1++;
  r2++;
  c1++;
  c2++;
  upd_rect(r1-1, c1-1, -1);
  upd_rect(r1, c1-1, -1);
  upd_rect(r1-1, c1, -1);
  upd_rect(r1, c1, -1);
  upd_rect(r2-1, c2-1, -1);
  upd_rect(r2, c2-1, -1);
  upd_rect(r2-1, c2, -1);
  upd_rect(r2, c2, -1);
  tabl[r1][c1]=b;
  tabl[r2][c2]=a;
  swap(rows[a], rows[b]);
  swap(cols[a], cols[b]);
  upd_rect(r1-1, c1-1, 1);
  upd_rect(r1, c1-1, 1);
  upd_rect(r1-1, c1, 1);
  upd_rect(r1, c1, 1);
  upd_rect(r2-1, c2-1, 1);
  upd_rect(r2, c2-1, 1);
  upd_rect(r2-1, c2, 1);
  upd_rect(r2, c2, 1);
  return query(1, 0, h*w-1, 0, h*w-1, 4);
}

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