Submission #1147473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147473		fryingduc	Mosaic (IOI24_mosaic)	C++20	100 / 100	105 ms	35516 KiB

mosaic

#include "mosaic.h"
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)
#endif

int n, q;
const int maxn = 2e5 + 5;
int cx[5][maxn], cy[5][maxn];
int px[5][maxn], py[5][maxn];
int d[5][5];
long long sum[maxn];
int a[maxn * 2];
long long ps[maxn * 2], pref[maxn * 2];

long long get_sum(int l, int r) {
  if (l > r || r < 0) return 0;
  return pref[r] - (l <= 0 ? 0 : pref[l - 1]);
}

long long get(int r, int c) {
  if (r < 0 || c < 0) return 0;
  long long res = get_sum(n - 5, n - 5 + c);
  res -= get_sum(n - 5 - r - 1, n - 5 + c - r - 1);
//  debug(r, c, res);
  return res;
}

vector<long long> mosaic(vector<int> x, vector<int> y, vector<int> qt, vector<int> qb, vector<int> ql, vector<int> qr) {
  q = (int)qt.size();
  n = (int)x.size();
  if (n < 5) {
    for (int i = 0; i < n; ++i) {
      d[0][i] = x[i];
      d[i][0] = y[i];
    }
    for (int i = 1; i < n; ++i) {
      for (int j = 1; j < n; ++j) {
        if (d[i - 1][j] || d[i][j - 1]) {
          d[i][j] = 0;
        } else {
          d[i][j] = 1;
        }
      }
    }
    vector<long long> res;
    for (int i = 0; i < q; ++i) {
      int cnt = 0;
      for (int r = qt[i]; r <= qb[i]; ++r) {
        for (int c = ql[i]; c <= qr[i]; ++c) {
          cnt += d[r][c];
        }
      }
      res.push_back(cnt);
    }
    return res;
  }
  for (int i = 0; i < n; ++i) {
    cx[0][i] = px[0][i] = x[i];
    cy[0][i] = py[0][i] = y[i];
    if (i > 0) {
      px[0][i] += px[0][i - 1];
      py[0][i] += py[0][i - 1];
    }
  }
  for (int ite = 1; ite < 5; ++ite) {
    cx[ite][0] = y[ite];
    cy[ite][0] = x[ite];
    for (int i = 1; i < n; ++i) {
      if (cx[ite][i - 1] || cx[ite - 1][i]) {
        cx[ite][i] = 0;
      } else {
        cx[ite][i] = 1;
      }
      if (cy[ite][i - 1] || cy[ite - 1][i]) {
        cy[ite][i] = 0;
      } else {
        cy[ite][i] = 1;
      }
    }
    for (int i = 0; i < n; ++i) {
      px[ite][i] = cx[ite][i];
      py[ite][i] = cy[ite][i];
      if (i > 0) {
        px[ite][i] += px[ite][i - 1];
        py[ite][i] += py[ite][i - 1];
      }
    }
  } 
  for (int i = n - 1; i >= 4; --i) {
    a[n - i - 1] = cy[4][i];
  }
  for (int i = 4; i < n; ++i) {
    a[n - 5 + (i - 4)] = cx[4][i];
  }
//  for (int i = 0; i < (n - 4) * 2 - 1; ++i) {
//    cout << a[i] << " ";
//  }
  for (int i = 0; i < (n - 4) * 2 - 1; ++i) {
    ps[i] = (i == 0 ? 0 : ps[i - 1]) + a[i];
    pref[i] = (i == 0 ? 0 : pref[i - 1]) + ps[i];
  }
  vector<long long> res;
  for (int i = 0; i < q; ++i) {
    long long cur = 0;
    int t = qt[i], b = qb[i], l = ql[i], r = qr[i];
    while (t < 4 and t <= b) {
      cur += px[t][r] - (l == 0 ? 0 : px[t][l - 1]);
      ++t;
    }
    while (l < 4 and l <= r) {
      cur += py[l][b] - (t == 0 ? 0 : py[l][t - 1]);
      ++l;
    }
    if (t > b || l > r) {
      res.push_back(cur);
      continue;
    }
    l -= 4, r -= 4, t -= 4, b -= 4;
    cur += get(b, r) - get(b, l - 1) - get(t - 1, r) + get(t - 1, l - 1);
    res.push_back(cur);
  }
  return res;
}

• 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