제출 #1239776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239776		nikd	자리 배치 (IOI18_seats)	C++20	25 / 100	4094 ms	47668 KiB

seats

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

struct node{
  int mn, mx;
};

struct seg{  
  node f(node a, node b){
    return node{min(a.mn, b.mn), max(a.mx, b.mx)};
  }
  int n; vector<node> t;
  void build(vector<int> &a){
    n = a.size(); t.resize(2*n);
    for(int i = 0; i<n; i++) t[i+n] = {a[i], a[i]};
    for(int i = n-1; i>0; i--) t[i] = f(t[i<<1],t[(i<<1)|1]);
    return;
  }
  void upd(int x, int i){
    for(t[i+=n] = {x, x}; i>>=1;) t[i] = f(t[i<<1], t[(i<<1)|1]);
    return;
  }
  node q(int l, int r){
    node sl = {INT_MAX, 0};
    for(l+=n, r+=n; l<=r; l>>=1, r>>=1){
      if(l&1) sl = f(sl, t[l++]);
      if(!(r&1)) sl = f(sl, t[r--]);
    }
    return sl;
  }
};


seg r, c;
int h, w;


void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  h = H; w = W;
  r.build(R); c.build(C);
  return;
}

int swap_seats(int a, int b) {
  int ca = c.t[a+c.n].mn;
  int cb = c.t[b+c.n].mn;
  int ra = r.t[a+r.n].mn;
  int rb = r.t[b+r.n].mn;
  c.upd(cb, a);
  c.upd(ca, b);
  r.upd(rb, a);
  r.upd(ra, b);
  auto get_rc = [&](int i)->int{
    node cc = c.q(0, i);
    node rr = r.q(0, i); 
    return (cc.mx-cc.mn+1)*(rr.mx-rr.mn+1);
  };
  int sol = 0;
  for(int i = 0; i<h*w; i++){
    int sz = get_rc(i);
    i = sz-1;
    if(i+1 == get_rc(i)) sol++;
  }
  return sol;
}

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