Submission #1203621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203621		abczz	Mosaic (IOI24_mosaic)	C++20	100 / 100	223 ms	55244 KiB

mosaic

#include "mosaic.h"
#include <iostream>
#include <vector>
#include <map>
#define ll long long

using namespace std;

map <ll, ll> mp;
ll k;
vector <ll> F, ps, V, ps1, ps2, ps3, rps1;

ll solve(ll x, ll y) {
  ll res = ps2[k-x] - (k+min(x, y)-x == ps2.size()-1 ? 0 : (ps2[k+min(x, y)-x+1] + rps1[k+min(x, y)-x+1] * min(x+1, y+1)));
  res += ps3[k+y] - (k+y-min(x, y) == 0 ? 0 : (ps3[k+y-min(x, y)-1]) + ps1[k+y-min(x, y)-1] * min(x+1, y+1));
  if (k+y-min(x, y)-1 >= k+min(x, y)-x+1) res += (ps1[k+y-min(x, y)-1] - ps1[k+min(x, y)-x]) * min(x+1, y+1);
  if (x == y) res -= V[k] * min(x+1, y+1);
  return res;
}
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R) {
  F.clear();
  ps.clear();
  V.clear();
  ps1.clear();
  ps2.clear();
  ps3.clear();
  rps1.clear();
  ll n = X.size(), q = T.size();
  F.resize(q);
  ps.resize(n);
  for (int i=0; i<n; ++i) ps[i] = X[i] + (i == 0 ? 0 : ps[i-1]);
  for (int i=0; i<q; ++i) {
    if (T[i] == 0) F[i] += ps[R[i]] - (L[i] == 0 ? 0 : ps[L[i]-1]);
  }
  for (int i=0; i<n; ++i) ps[i] = Y[i] + (i == 0 ? 0 : ps[i-1]);
  for (int i=0; i<q; ++i) {
    if (L[i] == 0) F[i] += ps[B[i]] - (T[i] == 0 ? ps[0] : ps[T[i]-1]);
    T[i] = max(T[i], 1);
    L[i] = max(L[i], 1);
  }
  for (int i=1; i<n; ++i) {
    X[i] = (((i == 1 ? Y[1] : X[i-1]) == 0 && X[i] == 0) ? 1 : 0);
  }
  Y[1] = X[1];
  for (int i=2; i<n; ++i) {
    Y[i] = ((Y[i-1] == 0 && Y[i] == 0) ? 1 : 0);
  }
  for (int i=1; i<n; ++i) ps[i] = X[i] + (i == 1 ? 0 : ps[i-1]);
  for (int i=0; i<q; ++i) {
    if (T[i] > B[i] || L[i] > R[i]) continue;
    if (T[i] == 1) F[i] += ps[R[i]] - (L[i] == 1 ? 0 : ps[L[i]-1]);
  }
  for (int i=1; i<n; ++i) ps[i] = Y[i] + (i == 1 ? 0 : ps[i-1]);
  for (int i=0; i<q; ++i) {
    if (T[i] > B[i] || L[i] > R[i]) continue;
    if (L[i] == 1) F[i] += ps[B[i]] - (T[i] == 1 ? ps[1] : ps[T[i]-1]);
    T[i] = max(T[i], 2);
    L[i] = max(L[i], 2);
    T[i] -= 2, B[i] -= 2, L[i] -= 2, R[i] -= 2;
  }
  for (int i=0; i<n-2; ++i) {
    if (i == 0) mp[0] = (X[2] == 0 && Y[2] == 0 ? 1 : 0);
    else if (i == 1) mp[-1] = (Y[3] == 0 && mp[0] == 0 ? 1 : 0), mp[1] = (mp[0] == 0 && X[3] == 0 ? 1 : 0);
    else {
      auto it = mp.begin();
      mp[-i] = (Y[i+2] == 0 && it->second == 0 ? 1 : 0);
      it = mp.end();
      it = prev(it);
      mp[i] = (X[i+2] == 0 && it->second == 0 ? 1 : 0);
    }
  }
  k = n-3;
  for (auto [x, y] : mp) {
    V.push_back(y);
  }
  ps1.resize(V.size());
  ps2.resize(V.size());
  ps3.resize(V.size());
  rps1.resize(V.size());
  for (int j=0; j<V.size(); ++j) {
    ps1[j] = V[j] + (j == 0 ? 0 : ps1[j-1]);
    ps3[j] = ps1[j] + (j == 0 ? 0 : ps3[j-1]);
  }
  for (int j=V.size()-1; j>=0; --j) {
    rps1[j] = V[j] + (j == V.size()-1 ? 0 : rps1[j+1]);
    ps2[j] = rps1[j] + (j == V.size()-1 ? 0 : ps2[j+1]);
  }
  for (int i=0; i<q; ++i) {
    if (T[i] > B[i] || L[i] > R[i]) continue;
    F[i] += solve(B[i], R[i]) - (T[i] == 0 ? 0 : solve(T[i]-1, R[i])) - (L[i] == 0 ? 0 : solve(B[i], L[i]-1)) + ((T[i] == 0 || L[i] == 0) ? 0 : solve(T[i]-1, L[i]-1));
  }
  return F;
}

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