제출 #1241325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241325		rxlfd314	모자이크 (IOI24_mosaic)	C++20	15 / 100	325 ms	35124 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 200005;

struct ST {
  int val;
  ST *lft, *rht;
  void update(const int i, const int v, const int tl = -mxN, const int tr = mxN) {
    if (tl == tr)
      val = v;
    else {
      int tm = (tl + tr) / 2;
      tm -= tm == tr;
      if (i <= tm) {
        if (!lft)
          lft = new ST{0, nullptr, nullptr};
        lft->update(i, v, tl, tm);
      } else {
        if (!rht)
          rht = new ST{0, nullptr, nullptr};
        rht->update(i, v, tm+1, tr);
      }
      val = (lft ? lft->val : 0) + (rht ? rht->val : 0);
    }
  }
  int query(const int ql, const int qr, const int tl = -mxN, const int tr = mxN) {
    if (tl > qr || tr < ql)
      return 0;
    if (ql <= tl && tr <= qr)
      return val;
    int tm = (tl + tr) / 2;
    tm -= tm == tr;
    return (lft ? lft->query(ql, qr, tl, tm) : 0) + (rht ? rht->query(ql, qr, tm+1, tr) : 0);
  }
};

vt<ll> mosaic(vt<int> X, vt<int> Y, vt<int> T, vt<int> B, vt<int> L, vt<int> R) {
  const int N = size(X), Q = size(T);
  if (false && N <= 5000) {
    vt<vt<int>> grid(N+1, vt<int>(N+1));
    FOR(i, 1, N) {
      grid[1][i] = X[i-1];
      grid[i][1] = Y[i-1];
    }
    vt<vt<int>> psum(N+1, vt<int>(N+1));
    FOR(i, 1, N)
      FOR(j, 1, N) {
        if (i > 1 && j > 1)
          grid[i][j] = !grid[i-1][j] & !grid[i][j-1];
        psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + grid[i][j];
      }
    vt<ll> ret(Q);
    FOR(i, 0, Q-1)
      ret[i] = psum[B[i]+1][R[i]+1] - psum[B[i]+1][L[i]] - psum[T[i]][R[i]+1] + psum[T[i]][L[i]];
    return ret;
  }
  if (*max_element(all(B)) == 0) {
    vt<int> psum(N+1);
    FOR(i, 0, N-1)
      psum[i+1] = psum[i] + X[i];
    vt<ll> ret(Q);
    FOR(i, 0, Q-1)
      ret[i] = psum[R[i]+1] - psum[L[i]];
    return ret;
  }
  if (*max_element(all(X)) == 0 && *max_element(all(Y)) == 0) {
    vt<ll> ret(Q);
    FOR(i, 0, Q-1) {
      L[i] += !L[i];
      T[i] += !T[i];
      ret[i] = (1ll * (B[i] - T[i] + 1) * (R[i] - L[i] + 1) + (T[i] + L[i] + 1 & 1)) / 2;
    }
    return ret;
  }
  vt<vt<int>> queries(N);
  FOR(i, 0, Q-1)
    queries[T[i]].push_back(i);
  
  vt<int> psum(N);
  psum[0] = X[0];
  FOR(i, 1, N-1)
    psum[i] = psum[i-1] + X[i];
  const auto transform = [&](const int y, const int n) {
    const vt<int> temp(X.begin(), X.begin() + n);
    psum[0] = X[0] = Y[y];
    FOR(i, 1, n-1) {
      X[i] = !X[i-1] & !temp[i];
      psum[i] = psum[i-1] + X[i];
    }
  };
  
  vt<ll> ret(Q);
  for (const auto &i : queries[0])
    ret[i] = psum[R[i]] - (L[i] ? psum[L[i]-1] : 0);
  if (N == 1)
    return ret;
  
  transform(1, N);
  for (const auto &i : queries[1])
    ret[i] = psum[R[i]] - (L[i] ? psum[L[i]-1] : 0);
  if (N == 2)
    return ret;
  
  transform(2, N);
  ST *st = new ST{0, nullptr, nullptr};
  set<int> zeros;
  FOR(i, 2, N-2)
    if (X[i] == X[i+1]) {
      assert(!X[i]);
      zeros.insert(i);
      st->update(i, 1);
    }
  FOR(i, 2, N-1) {
    if (X[0] == X[1])
      zeros.insert(-i + 2), st->update(-i + 2, 1);
    else if (X[1] == X[2])
      zeros.insert(-i + 3), st->update(-i + 3, 1);
    for (const auto &j : queries[i]) {
      const auto pp = [&](const int x) {
        if (x < 0)
          return 0;
        int res = 0;
        auto a = zeros.lower_bound(-i + 2);
        auto b = zeros.lower_bound(x - i + 3);
        if (a == b)
          res += (x + 1 + X[0]) / 2;
        if (a != b && *a + i - 2 < x) { // between a and b
          const int l = *a, r = *prev(b);
          res += (r - l - st->query(l+1, r)) / 2;
        }
        if (b != a && *prev(b) + i <= x) { // b to x
          const int k = *prev(b) + i;
          res += (x - k + 1) / 2;
        }
        if (*a + i - 2 < x) { // 0 to a
          const int k = *a + i - 2;
          res += (k + 1) / 2;
        }
        return res;
      };
      ret[j] = pp(R[j]) - pp(L[j] - 1);
      /*
      const auto it = zeros.lower_bound(L[j] - i + 3);
      if (it == zeros.begin()) {
        ret[j] = (X[0] ^ L[j]) & 1;
      } else {
        const int k = *prev(it) + i - 2;
        ret[j] = (max(k+1, L[j]) - k - 1) & 1;
      }*/
    }
    if (X[0] == X[1])
      zeros.erase(zeros.find(-i + 2)), st->update(-i + 2, 0);
    else if (X[1] == X[2])
      zeros.erase(zeros.find(-i + 3)), st->update(-i + 2, 0);
    if (i == N-1)
      break;
    transform(i+1, 4);
    if (X[2] == X[3])
      zeros.insert(-i + 3), st->update(-i + 3, 1);
  }
  return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 8 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22