Submission #3572323
Source Code Expand
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <iostream> #include <complex> #include <string> #include <algorithm> #include <numeric> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> #include <functional> #include <cassert> typedef long long ll; using namespace std; #define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl; #define mod 1000000007 //1e9+7(prime number) #define INF 1000000000 //1e9 #define LLINF 2000000000000000000LL //2e18 #define SIZE 100010 /* SuffixArray (Source: 蟻本) */ //O(N log^2 N) //pos[i] := 接頭辞の開始位置 //lcp[i] := lcp(s[pos[i]:n-1], s[pos[i-1]:n-1]) struct SuffixArray{ vector<int> pos, lcp; SuffixArray(const char *S){ int n = strlen(S), k; vector<int> rank(S, S+n), tmp(n); auto comp = [&](const int &i, const int &j){ if (rank[i] != rank[j]) return rank[i] < rank[j]; return (i+k <= n ? rank[i+k] : -1) < (j+k <= n ? rank[j+k] : -1); }; iota(pos.begin(), pos.end(), 0); for(k=1;k<n;k*=2){ sort(pos.begin(), pos.end(), comp); tmp[pos[0]] = 0; for(int i=1;i<n;i++) tmp[pos[i]] = tmp[pos[i-1]] + comp(pos[i-1], pos[i]); for(int i=0;i<n;i++) rank[i] = tmp[i]; } //LongestCommonPrefixArray lcp.resize(n); for(int i=0;i<n;i++) rank[pos[i]] = i; for(int i=0, h=0; i<n; i++) { if(rank[i] + 1 < n) { for(int j = pos[rank[i] + 1]; max(i, j) + h < n && S[i + h] == S[j + h]; h++); lcp[rank[i] + 1] = h; if(h > 0) h--; } } } int operator[](int k) const { return pos[k]; } }; ll sum(int t){ return (ll)t*(t+1)/2; } int main(){ char s[SIZE]; int n; scanf("%s", s); n = strlen(s); SuffixArray sa(s); ll ans = 0; for(int i=0;i<n;i++) ans += sum(n - sa[i]) - sum(sa.lcp[i]); printf("%lld\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 部分文字列 |
User | goodbaton |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2091 Byte |
Status | RE |
Exec Time | 103 ms |
Memory | 1152 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:86:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s", s); ^
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 15 | 0 / 35 | 0 / 50 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt |
Subtask1 | sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt |
Subtask2 | sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt |
Subtask3 | sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_1.txt | RE | 101 ms | 256 KB |
sample_2.txt | RE | 101 ms | 256 KB |
sample_3.txt | RE | 101 ms | 256 KB |
sub1_1.txt | RE | 100 ms | 256 KB |
sub1_2.txt | RE | 103 ms | 256 KB |
sub1_3.txt | RE | 101 ms | 256 KB |
sub1_4.txt | RE | 100 ms | 256 KB |
sub1_5.txt | RE | 102 ms | 256 KB |
sub1_6.txt | RE | 102 ms | 256 KB |
sub1_7.txt | RE | 103 ms | 256 KB |
sub1_8.txt | RE | 102 ms | 256 KB |
sub1_9.txt | RE | 102 ms | 256 KB |
sub2_1.txt | RE | 102 ms | 256 KB |
sub2_2.txt | RE | 102 ms | 256 KB |
sub3_1.txt | RE | 102 ms | 256 KB |
sub3_2.txt | RE | 101 ms | 384 KB |
sub3_3.txt | RE | 101 ms | 1152 KB |