제출 #1239129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239129		noyancanturk	Seats (IOI18_seats)	C++20	25 / 100	4094 ms	82500 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;

const int lim=1e6+100;

int n,h,w;
vector<int>v[lim];

vector<int>r,c;

struct MAX{
  inline static int cmp(const int& i,const int&j){
    if(i<j)return j;
    return i;
  }
};
struct MIN{
  inline static int cmp(const int& i,const int&j){
    if(i>j)return j;
    return i;
  }
};

template<typename T,int nullval>
struct ST{
  int tree[2*lim];
  ST(){
    for(int i=0;i<2*lim;i++)tree[i]=nullval;
  }
  int query(int l,int r){
    int ans=nullval;
    for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
      if(l&1)ans=T::cmp(ans,tree[l++]);
      if(r&1)ans=T::cmp(ans,tree[--r]);
    }
    return ans;
  }
  void update(int p,int val){
    p+=n;
    tree[p]=val;
    for(p>>=1;p;p>>=1)tree[p]=T::cmp(tree[p<<1],tree[p<<1|1]);
  }
};

ST<MIN,INT_MAX>cmin,rmin;
ST<MAX,INT_MIN>cmax,rmax;

void updateguy(int i){
  cmax.update(i,c[i]);
  cmin.update(i,c[i]);
  rmax.update(i,r[i]);
  rmin.update(i,r[i]);
}

void give_initial_chart(int H,int W,vector<int>R,vector<int>C){
  n=H*W;
  h=H;
  w=W;
  for(int i=0;i<H;i++){
    v[i].resize(W);
  }
  r=R,c=C;
  for(int i=0;i<n;i++){
    updateguy(i);
  }
}

int swap_seats(int x,int y){
  swap(v[r[x]][c[x]],v[r[y]][c[y]]);
  swap(r[x],r[y]);
  swap(c[x],c[y]);
  updateguy(x);
  updateguy(y);
  // for(int i=0;i<n;i++){
  //   cerr<<c[i]<<' '<<r[i]<<' '<<cmax.query(i,i)<<' '<<cmin.query(i,i)<<' '<<rmax.query(i,i)<<' '<<rmin.query(i,i)<<'\n';
  // }
  int ans=0,mxc=INT_MIN,mxr=INT_MIN,mnr=INT_MAX,mnc=INT_MAX;
  int i=0;
  while(i<n){
    mxc=cmax.query(0,i);
    mxr=rmax.query(0,i);
    mnc=cmin.query(0,i);
    mnr=rmin.query(0,i);
    int area=(mxc-mnc+1)*(mxr-mnr+1);
    // cerr<<i<<" :: "<<mxc<<' '<<mxr<<' '<<mnr<<' '<<mnc<<" :: "<<area<<'\n';;
    // assert(i+1<=area);
    if(i+1==area){
      ans++;
      i++;
    }else{
      i=area-1;
    }
  }
  return ans;
}

// std::vector<int> r;

// void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
//   r = R;
// }

// int swap_seats(int a, int b) {
//   return r[a];
// }

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