Submission #45046

#	Time	Username	Problem	Language	Result	Execution time	Memory
45046		Xellos	Klavir (COCI17_klavir)	C++14	160 / 160	318 ms	49988 KiB

klavir

#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N,M;
	cin >> N >> M;
	vector<int> A(M);
	for(int i =0; i < M; i++) {
		cin >> A[i];
		A[i]--;}
	long long mod =1000000007;
	vector<int> prev(M+1,0);
	for(int i =2; i <= M; i++) {
		prev[i] =prev[i-1];
		while(prev[i] > 0 && A[prev[i]] != A[i-1]) prev[i] =prev[prev[i]];
		if(A[prev[i]] == A[i-1]) prev[i]++;}
	vector<int> prev2(M+1);
	for(int i =0; i < M; i++) {
		prev2[i] =prev[i];
		if(A[i] == A[prev2[i]]) prev2[i] =prev2[prev2[i]];}
	vector<long long> E(M+1,0), sum(M+1,0);
	long long used[2] ={0,0};
	for(int i =0; i < M; i++) {
		E[i+1] =(E[i]-1)*N;
		int akt =prev[i];
		used[A[i]/60] |=1LL<<(A[i]%60);
		while(akt >= 0) {
			if(((used[A[akt]/60]>>(A[akt]%60))&1) == 0) {
				used[A[akt]/60] |=1LL<<(A[akt]%60);
				sum[i+1] +=E[akt+1];}
			if(akt == 0) break;
			akt =prev2[akt];}
		E[i+1] -=sum[i+1];
		used[0] =used[1] =0;
		E[i+1] %=mod;}
	for(int i =1; i <= M; i++) {
		long long x =(E[0]-E[i])%mod;
		if(x < 0) x +=mod;
		cout << x << "\n";}
	}

// look at my code
// my code is amazing

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16