oj.uz

Submission #45046

# Submission time Handle Problem Language Result Execution time Memory
45046 2018-04-11T05:08:19 Z Xellos Klavir (COCI17_klavir) C++14
160 / 160
 318 ms 49988 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 496 KB Output is correct
2 Correct 4 ms 496 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 496 KB Output is correct
2 Correct 2 ms 704 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 704 KB Output is correct
2 Correct 2 ms 704 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 704 KB Output is correct
2 Correct 2 ms 704 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 704 KB Output is correct
2 Correct 2 ms 704 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4548 KB Output is correct
2 Correct 197 ms 37160 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 42004 KB Output is correct
2 Correct 206 ms 42004 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 45988 KB Output is correct
2 Correct 195 ms 45988 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 49988 KB Output is correct
2 Correct 202 ms 49988 KB Output is correct