제출 #1239017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239017		noyancanturk	Seats (IOI18_seats)	C++20	5 / 100	4094 ms	84168 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{
  int tree[4*lim];
  int P,VAL;
  void update(int l,int r,int node){
    if(l==r){
      tree[node]=VAL;
      return;
    }
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)update(l,mid,child);
    else update(mid+1,r,child|1);
    tree[node]=min(tree[child],tree[child|1]);
  }
  void update(int p,int val){
    P=p,VAL=val;
    update(0,lim-1,1);
  }
  int L,R;
  void query(int l,int r,int node){
    if(L<=l&&r<=R){
      if(VAL>tree[node])VAL=tree[node];
      return;
    }
    int mid=l+r>>1,child=node<<1;
    if(L<=mid)query(l,mid,child);
    if(mid+1<=R)query(mid+1,r,child|1);
  }
  int query(int l,int r){
    L=l,R=r,VAL=INT_MAX;
    query(0,lim-1,1);
    return VAL;
  }
}rmin,cmin;
struct{
  int tree[4*lim];
  int P,VAL;
  void update(int l,int r,int node){
    if(l==r){
      tree[node]=VAL;
      return;
    }
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)update(l,mid,child);
    else update(mid+1,r,child|1);
    tree[node]=max(tree[child],tree[child|1]);
  }
  void update(int p,int val){
    P=p,VAL=val;
    update(0,lim-1,1);
  }
  int L,R;
  void query(int l,int r,int node){
    if(L<=l&&r<=R){
      if(VAL<tree[node])VAL=tree[node];
      return;
    }
    int mid=l+r>>1,child=node<<1;
    if(L<=mid)query(l,mid,child);
    if(mid+1<=R)query(mid+1,r,child|1);
  }
  int query(int l,int r){
    L=l,R=r,VAL=INT_MIN;
    query(0,lim-1,1);
    return VAL;
  }
}rmax,cmax;

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: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30