제출 #1217946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217946		dosts	Mosaic (IOI24_mosaic)	C++20	12 / 100	149 ms	38552 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

vi mosaic(vector<int32_t> X, vector<int32_t> Y,
                              vector<int32_t> T, vector<int32_t> B,
                              vector<int32_t> L, vector<int32_t> R) {
  int N = X.size(),Q = T.size();
  int rows[4][N+1]{},cols[4][N+1]{};
  for (int i = 1;i<=N;i++) rows[1][i] = X[i-1];
  for (int i = 1;i<=N;i++) cols[1][i] = Y[i-1];
  for (int i=2;i<=N && i <= 3;i++) rows[i][1] = Y[i-1];
  for (int i=2;i<=N && i<=3;i++) cols[i][1] = X[i-1];
  set<int> diag;
  for (int i = 2;i<=3;i++) {
    for (int j = 2;j<=N;j++) {
      rows[i][j] = (!rows[i-1][j] && !rows[i][j-1]);
      if (rows[i][j]) diag.insert(i-j);
    }
  }
  for (int i = 2;i<=3;i++) {
    for (int j = 2;j<=N;j++) {
      cols[i][j] = (!cols[i-1][j] && !cols[i][j-1]);
      if (cols[i][j]) diag.insert(j-i);
    }
  }
  if (N >= 4) {
    int prv = cols[3][4];
    for (int i = 4;i<=4;i++) {
      for (int j = 4;j<=N;j++) {
        prv = (!rows[3][j] && !prv);
        if (prv) diag.insert(i-j);
      }
    }
    prv = rows[3][4];
    for (int i = 4;i<=4;i++) {
      for (int j = 4;j<=N;j++) {
        prv = (!cols[3][j] && !prv);
        if (prv) {
          diag.insert(j-i);
        }
      }
    }
  }
  vi vals;
  auto idx = [&](int x) {
    return upper_bound(all(vals),x)-vals.begin();
  };
  for (int i=1-N;i<=N-1;i++) vals.push_back(i);
  sort(all(vals));
  vi pref(vals.size()+1,0ll);
  for (auto it : diag) pref[idx(it)] = 1;
  for (int i=1;i<=big(vals);i++) pref[i]+=pref[i-1];
  vi ans(Q,0);
  for (int i=1;i<=3;i++) {
    for (int j = 2;j<=N;j++) rows[i][j] += rows[i][j-1];
  }
  for (int i=1;i<=3;i++) {
    for (int j = 2;j<=N;j++) cols[i][j] += cols[i][j-1];
  }
  for (int i = 0;i<Q;i++) {
    L[i]++,R[i]++,T[i]++,B[i]++;
    for (int r = T[i];r<=3 && r <= B[i];r++) ans[i] += rows[r][R[i]]-rows[r][L[i]-1];
    T[i] = max(T[i],4);
    if (T[i] > B[i]) continue;
    for (int c = L[i];c<=3 && c <= R[i];c++) ans[i] += cols[c][B[i]]-cols[c][T[i]-1];
    L[i] = max(L[i],4);
    if (L[i] > R[i]) continue;
    int sz = (R[i]-L[i]+1)*(B[i]-T[i]+1);
    if ((L[i]+R[i])%2) ans[i] += (sz)/2;
    else ans[i] += (sz+1)/2;
  }
  return ans;
}

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