Submission #75485

#	Time	Username	Problem	Language	Result	Execution time	Memory
75485		C_SUNSHINE	Seats (IOI18_seats)	C++14	100 / 100	1618 ms	102972 KiB

seats

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include "seats.h"
using namespace std;

const int maxn=1000005;

const int dx[4]={0,0,1,1},dy[4]={0,1,0,1};

int H,W,NUM;
int val[maxn],presum[maxn];
vector<int> R,C;
int S[maxn],T[maxn];

struct node
{
  int dta;
  int s,cnt;
  node *lc,*rc;
  
  void tagdta(const int &c)
  {
    s+=c;
    dta+=c;
  }
  
  void downdate()
  {
    if(dta)
    {
      if(lc)lc->tagdta(dta);
      if(rc)rc->tagdta(dta);
      dta=0;
    }
  }
  
  void update()
  {
    if(lc->s<rc->s)
    {
      s=lc->s;
      cnt=lc->cnt;
    }
    else if(rc->s<lc->s)
    {
      s=rc->s;
      cnt=rc->cnt;
    }
    else
    {
      s=lc->s;
      cnt=lc->cnt+rc->cnt;
    }
  }
  
  void Add(int l,int r,const int &a,const int &b,const int &c)
  {
    if(l>=a&&r<=b)
    {
      tagdta(c);
      return;
    }
    int mid=l+r>>1;
    downdate();
    if(a<=mid)lc->Add(l,mid,a,b,c);
    if(b>mid)rc->Add(mid+1,r,a,b,c);
    update();
  }
  
}ndl[maxn*2],*ns=ndl,*root;

node* build(int l,int r)
{
  node *x=ns++;
  x->dta=0;
  if(l==r)
  {
    x->s=presum[l];
    x->cnt=1;
    x->lc=x->rc=NULL;
  }
  else
  {
    int mid=l+r>>1;
    x->lc=build(l,mid);
    x->rc=build(mid+1,r);
    x->update();
  }
  return x;
}

int& seat(int *s,const int &x,const int &y)
{
  if(x>=0&&x<H&&y>=0&&y<W)return s[x*W+y];
  return NUM;
}

const int ValTable[2][3]={
  {1,-1,-1},
  {1,1,-1}
};
int CalcVal(int *s,const int &x,const int &y,const int w=15)
{
  int res=0;
  for(int k=0;k<4;k++)
    if(w>>k&1)
    {
      int i=x-1+dx[k];
      int j=y-1+dy[k];
      int t=seat(s,x,y);
      int a=seat(s,i+dx[k^1],j+dy[k^1]);
      int b=seat(s,i+dx[k^2],j+dy[k^2]);
      int c=seat(s,i+dx[k],j+dy[k]);
      res+=ValTable[c<t][(a<t)+(b<t)];
    }
  //cout<<endl;
  return res;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
  ::H=H;
  ::W=W;
  NUM=H*W;
  ::R.assign(NUM,0);
  ::C.assign(NUM,0);
  for(int i=0;i<NUM;i++)
  {
    ::R[i]=R[i];
    ::C[i]=C[i];
    seat(S,R[i],C[i])=seat(T,R[i],C[i])=i;
  }
  for(int i=0;i<NUM;i++)
  {
    val[i]=CalcVal(S,R[i],C[i]);
    if(i==0)presum[i]=val[i];
    else presum[i]=presum[i-1]+val[i];
  }
  //for(int i=0;i<NUM;i++)cout<<val[i]<<' ';cout<<endl;
  root=build(0,NUM-1);
}

void UpdateVal(int x,int v)
{
  root->Add(0,NUM-1,x,NUM-1,v-val[x]);
  val[x]=v;
}

int swap_seats(int a, int b)
{
  swap(seat(T,R[a],C[a]),seat(T,R[b],C[b]));
  vector<int> p;
  for(int i=-1;i<=1;i++)
    for(int j=-1;j<=1;j++)
      {
        int t;
        t=seat(T,R[a]+i,C[a]+j);
        if(t!=NUM)p.push_back(t);
        t=seat(T,R[b]+i,C[b]+j);
        if(t!=NUM)p.push_back(t);
      }
  swap(R[a],R[b]);
  swap(C[a],C[b]);
  sort(p.begin(),p.end());
  p.erase(unique(p.begin(),p.end()),p.end());
  for(auto x:p)
  {
    UpdateVal(x,CalcVal(T,R[x],C[x]));
  }
  swap(seat(S,R[a],C[a]),seat(S,R[b],C[b]));
  if(root->s!=4)return 0;
  return root->cnt;
}

Compilation message (stderr)

seats.cpp: In member function 'void node::Add(int, int, const int&, const int&, const int&)':
seats.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=l+r>>1;
             ~^~
seats.cpp: In function 'node* build(int, int)':
seats.cpp:88:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=l+r>>1;
             ~^~

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