Submission #1143086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143086		ag_1204	Mosaic (IOI24_mosaic)	C++20	0 / 100	117 ms	20908 KiB

mosaic

#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pb push_back

vi mosaic(vector<signed> X,vector<signed> Y,vector<signed> T,vector<signed> B,vector<signed> L,vector<signed> 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;
}

• 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