제출 #1312463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312463		exoworldgd	모자이크 (IOI24_mosaic)	C++20	0 / 100	87 ms	18356 KiB

mosaic

#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-10]-sum[l[i]-t[i]+n-11]-sum[r[i]-b[i]+n-11]+(l[i]-b[i]+n>=12?sum[l[i]-b[i]+n-12]:0);
	return c;
}

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