제출 #295222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295222		TheLorax	자리 배치 (IOI18_seats)	C++11	0 / 100	4058 ms	113272 KiB

seats

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

#define F first
#define S second
#define SZ(a) ((int)(a).size())
#define PB push_back
#define ALL(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;


ii mip(ii a, ii b){
  return {min(a.F,b.F),min(a.S,b.S)};
}

ii mxp(ii a, ii b){
  return {max(a.F,b.F),max(a.S,b.S)};
}

struct mix{
  ii  mx, mi;

  mix(ii p){
    mx=p;
    mi=p;
  }
  mix(){ }
  mix(ii a, ii b){
    mx=a, mi=b;
  }

  ll area(){
    return (mx.F-mi.F+1)*(mx.S-mi.S+1);
  }
};

mix comb(mix a, mix b){
  mix r;
  r.mx=mxp(a.mx, b.mx);
  r.mi=mip(a.mi, b.mi);
  return r;
}

std::vector<ii> p;
std::vector<mix> heap;
int h, w, np2;

void upd(int i, ii p, int a=0, int b=np2, int h=1){
  if(i<a || b<=i)
    return;
  if(b-a==1){
    heap[h]=mix(p);
    return;
  }
  upd(i,p,a,(a+b)/2,h*2);
  upd(i,p,(a+b)/2,b,h*2+1);
  heap[h]=comb(heap[2*h],heap[2*h+1]);
}

mix que(int i, int j, int a=0, int b=np2, int h=1){
  if(j<=a || b<=i)
    return mix({0,0},{h,w});
  if(i<=a && b<=j)
    return heap[h];
  return comb(que(i,j,a,(a+b)/2,h*2),que(i,j,(a+b)/2,b,h*2+1));
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  h=H; w=W;
  np2=1;
  while (np2<h*w)
    np2<<=1;
  p.resize(h*w);
  heap.resize(np2*2);
  for(int i=0; i<h*w; i++)
    heap[i+np2]=p[i]={R[i],C[i]};
  for(int i=np2-1; i>0; i--)
    heap[i]=comb(heap[i*2],heap[i*2+1]);
}

int swap_seats(int a, int b) {
  swap(p[a],p[b]);
  upd(a,p[a]);
  upd(b,p[b]);
  int cc=0;
  for(int i=0; i<h*w; i++){
    int a=que(0,i+1).area();
    if(a==i+1)
      cc++;
    else
      i=a-2;
  }
  return cc;
}

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