제출 #124735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
124735		dragonslayerit	자리 배치 (IOI18_seats)	C++14	5 / 100	4100 ms	75732 KiB

seats

#include "seats.h"
#include <tuple>
#include <algorithm>
#include <iostream>

static const int INF=1e9+7;

struct Node{
  int max[4];
}st[2000000];
int N,H,W;

std::vector<std::tuple<int,int,int> > rectangles;

void pull(int i){
  for(int k=0;k<4;k++){
    st[i].max[k]=std::max(st[i<<1].max[k],st[i<<1|1].max[k]);
  }
}

void build(int i){
  for(i+=N;i>1;i>>=1){
    pull(i>>1);
  }
}

int query(int k,int b){
  int a=0;
  int res=-INF;
  for(a+=N,b+=N;a<b;a>>=1,b>>=1){
    if(a&1) res=std::max(res,st[a++].max[k]);
    if(b&1) res=std::max(res,st[--b].max[k]);
  }
  return res;
}

void give_initial_chart(int h, int w, std::vector<int> R, std::vector<int> C) {
  H=h;
  W=w;
  N=h*w;
  for(int i=0;i<N;i++){
    st[i+N].max[0]=R[i];
    st[i+N].max[1]=-R[i];
    st[i+N].max[2]=C[i];
    st[i+N].max[3]=-C[i];
  }
  for(int i=N-1;i>0;i--){
    pull(i);
  }
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      rectangles.emplace_back(i*j,i,j);
    }
  }
  std::sort(rectangles.begin(),rectangles.end());
}

int swap_seats(int a, int b) {
  for(int k=0;k<4;k++){
    std::swap(st[a+N].max[k],st[b+N].max[k]);
  }
  build(a),build(b);
  int cnt=0;
  for(auto rect:rectangles){
    int area=std::get<0>(rect);
    int h=std::get<1>(rect);
    int w=std::get<2>(rect);
    if(query(0,area)+query(1,area)==h-1&&
       query(2,area)+query(3,area)==w-1){
      //std::cerr<<"RECT: "<<h<<"x"<<w<<std::endl;
      cnt++;
    }
  }
  return cnt;
}

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