| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1143085 | ag_1204 | Mosaic (IOI24_mosaic) | C++20 | 0 ms | 0 KiB |
#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pb push_back
vi mosaic(vi X,vi Y,vi T,vi B,vi L,vi R) {
int n=size(X),q=size(T);
vi C(q,0);
vi fst;
for (int i=n-1;i>0;i--) fst.pb(Y[i]);
for (int i=0;i<n;i++) fst.pb(X[i]);
for (int s=0;s<10;s++) {
vi sum(2*(n-s),0);
partial_sum(fst.begin(),fst.end(),sum.begin()+1);
for (int i=0;i<q;i++) {
if (T[i]==s) {
C[i]+=sum[R[i]-T[i]+n-s]-sum[L[i]-T[i]+n-s-1];
T[i]++;
}
if (L[i]==s) {
C[i]+=sum[L[i]-T[i]+n-s]-sum[L[i]-B[i]+n-s-1];
L[i]++;
}
}
if (s==n-1) return C;
vi snd(2*(n-s)-3,0);
for (int i=0;i<n-s-1;i++) {
if (i) {
snd[i+n-s-2]=!fst[i+n-s] && !snd[i+n-s-3];
snd[n-s-2-i]=!fst[n-s-i-2] && !snd[n-s-1-i];
} else {
snd[i+n-s-2]=!fst[i+n-s] && !fst[n-s-2];
snd[n-s-2-i]=!fst[n-s-i-2] && !fst[n-s];
}
}
fst=snd;
}
vi sum(2*n-20,0);
partial_sum(fst.begin(),fst.end(),sum.begin()+1);
partial_sum(sum.begin(),sum.end(),sum.begin());
for (int i=0;i<q;i++) {
C[i]+=sum[R[i]-T[i]+n-10];
C[i]-=sum[L[i]-T[i]+n-11]+sum[R[i]-B[i]+n-11];
if (L[i]-B[i]+n-12>=0) C[i]+=sum[L[i]-B[i]+n-12];
}
return C;
}