| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1312461 | exoworldgd | 모자이크 (IOI24_mosaic) | C++20 | 0 ms | 0 KiB |
#include "mosaic.h"
#include<bits/stdc++.h>
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0);
using namespace std;
vector<ll>mosaic(vector<int>x,vector<int>y,vector<int>t,vector<int>b,vector<int>l,vector<int>r){
int n=x.size(),q=t.size();
vector<ll>c(q,0);
vector<int>h(n-1<<1|1,0),sum(n-20,0);
copy(y.rbegin(),y.rend(),h.begin()),copy(x.begin()+1,x.end(),h.begin()+n);
for(int s=0;s<10;s++){
vector<ll>sum(n-s<<1,0);
partial_sum(h.begin(),h.end(),sum.begin()+1);
for(int i=0;i<q;i++)if(t[i]<=b[i]&&l[i]<=r[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;
vector<int>nxt(n-s-2<<1|1,0);
for(int i=0;i<n-s-1;i++)nxt[i+n-s-2]=!h[i+n-s]&&!(i?nxt[i+n-s-3]:h[n-s-2]),nxt[n-s-2-i]=!h[n-s-i-2]&&!(i?nxt[n-s-1-i]:h[n-s]);
h=nxt;
}
partial_sum(h.begin(),h.end(),sum.begin()+1),partial_sum(sum.begin(),sum.end(),sum.begin());
for(int i=0;i<q;i++)if(t[i]<=b[i]&&l[i]<=r[i])c[i]+=sum[r[i]-t[i]+n-S]-sum[l[i]-t[i]+n-S-1]-sum[r[i]-b[i]+n-S-1]+(l[i]-b[i]+n>=12?sum[l[i]-b[i]+n-12]:0);
return c;
}
