제출 #1241224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241224		rxlfd314	모자이크 (IOI24_mosaic)	C++20	37 / 100	203 ms	204316 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)


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 (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;
  }
}

컴파일 시 표준 에러 (stderr) 메시지

mosaic.cpp: In function 'vt<long long int> mosaic(vt<int>, vt<int>, vt<int>, vt<int>, vt<int>, vt<int>)':
mosaic.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
   55 | }
      | ^

• 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: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22