제출 #1139484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139484		Mousa_Aboubaker	Seats (IOI18_seats)	C++20	11 / 100	4101 ms	317776 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> a;
vector<pair<int, int>> b;

template <typename F>
struct SegmentTree2D
{
  int n, m, init, to;
  vector<vector<int>> seg;
  vector<vector<int>> a;
  F func;
  void build(int tr, int dr, int lc, int rc, int t1, int t2)
  {
    if(tr == dr)
    {
      if(lc == rc)
      {
        seg[t1][t2] = a[tr][lc];
        return;
      }
      int md = (lc + rc) / 2;
      build(tr, dr, lc, md, t1, t2 * 2);
      build(tr, dr, md + 1, rc, t1, t2 * 2 + 1);
      seg[t1][t2] = func(seg[t1][t2 * 2], seg[t1][t2 * 2 + 1]);
      return;
    }
    int md = (tr + dr) / 2;
    build(tr, md, lc, rc, t1 * 2, t2);
    build(md + 1, dr, lc, rc, t1 * 2 + 1, t2);
    for(int i = 0; i < (int)seg[t1].size(); i++)
    {
      seg[t1][i] = func(seg[t1 * 2][i], seg[t1 * 2 + 1][i]);
    }
  }
  void initialization(vector<vector<int>> _a, int _init, F _func)
  {
    init = _init;
    func = _func;
    a = _a;
    n = (int)a.size();
    m = (int)a[0].size();
    // cout << func(1, 1e9) << '\n';
    seg.assign(n * 8, vector<int>(m * 8, init));
    build(0, n - 1, 0, m - 1, 1, 1);
  }
  void update(int x, int y, int val, int tr, int dr, int lc, int rc, int t1, int t2)
  {
    if(tr == dr)
    {
      if(lc == rc)
      {
        to = t2;
        seg[t1][t2] = val;
        return;
      }
      int md = (lc + rc) / 2;
      if(y <= md)
        update(x, y, val, tr, dr, lc, md, t1, t2 * 2);
      else
        update(x, y, val, tr, dr, md + 1, rc, t1, t2 * 2 + 1);
      seg[t1][t2] = func(seg[t1][t2 * 2], seg[t1][t2 * 2 + 1]);
      return;
    }
    int md = (tr + dr) / 2;
    if(x <= md)
      update(x, y, val, tr, md, lc, rc, t1 * 2, t2);
    else
      update(x, y, val, md + 1, dr, lc, rc, t1 * 2 + 1, t2);
    for(int i = to; i > 0; i /= 2)
      seg[t1][i] = func(seg[t1 * 2][i], seg[t1 * 2 + 1][i]);
  }
  void update(int x, int y, int val)
  {
    update(x, y, val, 0, n - 1, 0, m - 1, 1, 1);
  }
  int query(int r1, int r2, int c1, int c2, int tr, int dr, int lc, int rc, int t1, int t2)
  {
    if(r2 < tr or dr < r1)
      return init;
    if(r1 <= tr and dr <= r2)
    {
      if(c2 < lc or rc < c1)
        return init;
      if(c1 <= lc and rc <= c2)
        return seg[t1][t2];
      int md = (lc + rc) / 2;
      return func(
        query(r1, r2, c1, c2, tr, dr, lc, md, t1, t2 * 2),
        query(r1, r2, c1, c2, tr, dr, md + 1, rc, t1, t2 * 2 + 1)
      );
    }
    int md = (tr + dr) / 2;
    return func(
      query(r1, r2, c1, c2, tr, md, lc, rc, t1 * 2, t2),
      query(r1, r2, c1, c2, md + 1, dr, lc, rc, t1 * 2 + 1, t2)
    );
  }
  int query(int r1, int r2, int c1, int c2)
  {
    return query(r1, r2, c1, c2, 0, n - 1, 0, m - 1, 1, 1);
  }
};

SegmentTree2D<function<int (int, int)>> mx;

int n, m;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  n = H, m = W;
  a.assign(H, vector<int>(W));
  for(int i = 0; i < H * W; i++)
    a[R[i]][C[i]] = i;
  /* for(int i = 0; i < H; i++)
  {
    for(int j = 0; j < W; j++)
    {
      cout << a[i][j] << ' ';
    }
    cout << '\n';
  } */
  b.resize(H * W);
  for(int i = 0; i < H * W; i++)
    b[i] = {R[i], C[i]};
  mx.initialization(a, -1e9, [&](int l, int r)
  {
    return max(l, r);
  });
  /* for(int i = 0; i < (int)a.size(); i++)
  {
    for(int j = 0; j < (int)a[0].size(); j++)
    {
      cout << "( " << mn.query(i, i, j, j) << ' ' << mx.query(i, i, j, j) << " ), ";
    }
    cout << '\n';
  } */
}

int swap_seats(int l, int r) {
  int x1 = b[l].first, y1 = b[l].second;
  int x2 = b[r].first, y2 = b[r].second;
  // mx.update(x1, y1, r);
  // mx.update(x2, y2, l);
  swap(a[x1][y1], a[x2][y2]);
  b[l] = {x2, y2};
  b[r] = {x1, y1};
  /* for(int i = 0; i < (int)a.size(); i++)
  {
    for(int j = 0; j < (int)a[0].size(); j++)
    {
      cout << "( " << mn.query(i, i, j, j) << ' ' << mx.query(i, i, j, j) << " ), ";
    }
    cout << '\n';
  } */

  x1 = y1 = 1e9;
  x2 = y2 = -1e9;
  int res = 0;
  for(int i = 0; i < (int)b.size(); i++)
  {
    x1 = min(x1, b[i].first);
    y1 = min(y1, b[i].second);
    x2 = max(x2, b[i].first);
    y2 = max(y2, b[i].second);
    int maxi = (x2 - x1 + 1) * (y2 - y1 + 1) - 1;
    // f(mx.query(x1, x2, y1, y2) == maxi)
    if(maxi == i)
    {
      res++;
    }
  }
  return res;
}

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