Submission #191314

#	Time	Username	Problem	Language	Result	Execution time	Memory
191314		baluteshih	Seats (IOI18_seats)	C++14	100 / 100	1918 ms	123256 KiB

seats

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

const int MAXN = 1000005;

struct node {
  int min_val, min_cnt, lazy_tag;
}tr[MAXN * 4];

pair<int, int> seat[MAXN];
vector<vector<int>> mp;
int tags[MAXN], type, HW;
int dx[4] = {0, -1, 0 ,-1}, dy[4] = {0, 0, -1, -1};

void merge(node &u, node lch, node rch) {
  if(lch.min_val > rch.min_val)
    swap(lch,rch);
  u.min_val = lch.min_val;
  u.min_cnt = lch.min_cnt;
  if(lch.min_val == rch.min_val)
    u.min_cnt += rch.min_cnt;
}

void push_down(node &u, node &lch, node &rch) {
  lch.min_val += u.lazy_tag;
  lch.lazy_tag += u.lazy_tag;
  rch.min_val += u.lazy_tag;
  rch.lazy_tag += u.lazy_tag;
  u.lazy_tag = 0;
}

void build(int idx, int lb, int rb) {
  if(lb == rb) {
    tr[idx].min_val = tags[lb];
    tr[idx].min_cnt = 1;
    tr[idx].lazy_tag = 0;
    return;
  }
  int mid = (lb + rb) / 2;
  build(idx * 2, lb, mid);
  build(idx * 2 + 1, mid + 1, rb);
  merge(tr[idx], tr[idx * 2], tr[idx * 2 + 1]);
}

void modify(int idx, int lb, int rb, int ql, int qr, int val) {
  if(ql <= lb && rb <= qr) {
    tr[idx].min_val += val;
    tr[idx].lazy_tag += val;
    return;
  } 
  push_down(tr[idx], tr[idx * 2], tr[idx * 2 + 1]);
  int mid = (lb + rb) / 2;
  if(ql <= mid) 
    modify(idx * 2, lb, mid, ql, qr, val);
  if(qr > mid)
    modify(idx * 2 + 1, mid + 1, rb, ql, qr, val);
  merge(tr[idx], tr[idx * 2], tr[idx * 2 + 1]);
}

void add_segment(int lb, int rb, int val) {
  if(lb == rb) return;
  if(type == 0) {
    tags[lb] += val;
    tags[rb] -= val;
  }
  else
    modify(1, 1, HW, lb, rb - 1, val);
}

void pattern(int x, int y, int val) {
  int a[4] = {mp[x][y], mp[x+1][y], mp[x][y+1], mp[x+1][y+1]};
  sort(a, a + 4);
  add_segment(a[0], a[1], val);
  add_segment(a[2], a[3], val);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  HW = H * W;
  mp.resize(H + 2, vector<int>(W + 2, HW + 1));
  for(int i = 0; i < HW; ++i) {
    mp[R[i] + 1][C[i] + 1] = i + 1;
    seat[i + 1] = make_pair(R[i] + 1, C[i] + 1);
  }
  for(int i = 0; i <= H; ++i)
    for(int j = 0; j <= W; ++j)
      pattern(i, j, 1);
  for(int i = 1; i <= HW; ++i)
    tags[i] += tags[i-1];
  build(1, 1, HW);
  type = 1;
}

//swap_seats會回傳每次交換完的美麗程度
int swap_seats(int a, int b) {
  ++a, ++b;

  for(int i = 0; i < 4; ++i)
    pattern(seat[a].first + dx[i], seat[a].second + dy[i], -1);
  mp[seat[a].first][seat[a].second] = b;
  for(int i = 0; i < 4; ++i)
    pattern(seat[a].first + dx[i], seat[a].second + dy[i], 1);
  
  for(int i = 0; i < 4; ++i)
    pattern(seat[b].first + dx[i], seat[b].second + dy[i], -1);
  mp[seat[b].first][seat[b].second] = a;
  for(int i = 0; i < 4; ++i)
    pattern(seat[b].first + dx[i], seat[b].second + dy[i], 1);
  
  swap(seat[a], seat[b]);
  return tr[1].min_cnt;
}

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