제출 #1238894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238894		simplemind_31	모자이크 (IOI24_mosaic)	C++20	22 / 100	239 ms	208684 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef long long ll;
vll C;
bitset<5001> mat[5001];
ll psum[5001][5001];
int N,Q;
vll mosaic(vi X, vi Y,vi T, vi B,vi L, vi R){
  N=X.size();
  for(int i=0;i<N;i++){
    mat[1][i+1]=1-X[i];
    mat[i+1][1]=1-Y[i];
  }
  for(int i=2;i<=N;i++){
    for(int j=2;j<=N;j++){
      mat[i][j]=!(mat[i][j-1]&mat[i-1][j]);
    }
  }
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++){
      psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+(mat[i][j]==0);
    }
  }
  C.resize(Q=T.size());
  for(int i=0;i<Q;i++){
    C[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 C;
}

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