# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
45046 |
2018-04-11T05:08:19 Z |
Xellos |
Klavir (COCI17_klavir) |
C++14 |
|
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
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
496 KB |
Output is correct |
2 |
Correct |
4 ms |
496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
496 KB |
Output is correct |
2 |
Correct |
2 ms |
704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
704 KB |
Output is correct |
2 |
Correct |
2 ms |
704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
704 KB |
Output is correct |
2 |
Correct |
2 ms |
704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
704 KB |
Output is correct |
2 |
Correct |
2 ms |
704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
4548 KB |
Output is correct |
2 |
Correct |
197 ms |
37160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
277 ms |
42004 KB |
Output is correct |
2 |
Correct |
206 ms |
42004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
318 ms |
45988 KB |
Output is correct |
2 |
Correct |
195 ms |
45988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
216 ms |
49988 KB |
Output is correct |
2 |
Correct |
202 ms |
49988 KB |
Output is correct |