Submission #3567785
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] := 接頭辞の開始位置
struct SuffixArray{
int n, k;
vector<int> rank, tmp, pos, lcp;
bool comp(int i, 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);
}
SuffixArray(const char *S){
int n = strlen(S);
tmp.resize(n);
pos.resize(n);
iota(pos.begin(), pos.end(), 0);
for(int i=0;i<n;i++) rank.push_back(S[i]);
for(k=1;k<n;k*=2){
sort(pos.begin(), pos.end(), [&](const int &a, const int &b){ return comp(a,b); });
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 = sum(n - sa[0]);
for(int i=1;i<n;i++)
ans += sum(n - sa[i]) - sum(sa.lcp[i-1]);
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time
2018-11-09 15:43:40+0900
Task
E - 部分文字列
User
goodbaton
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2136 Byte
Status
WA
Exec Time
76 ms
Memory
2040 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
AC
1 ms
256 KB
sample_2.txt
AC
1 ms
256 KB
sample_3.txt
AC
1 ms
256 KB
sub1_1.txt
WA
1 ms
256 KB
sub1_2.txt
AC
1 ms
256 KB
sub1_3.txt
WA
1 ms
256 KB
sub1_4.txt
WA
1 ms
256 KB
sub1_5.txt
WA
1 ms
256 KB
sub1_6.txt
WA
1 ms
256 KB
sub1_7.txt
WA
1 ms
256 KB
sub1_8.txt
WA
1 ms
256 KB
sub1_9.txt
WA
1 ms
256 KB
sub2_1.txt
WA
2 ms
256 KB
sub2_2.txt
WA
2 ms
256 KB
sub3_1.txt
WA
3 ms
384 KB
sub3_2.txt
WA
11 ms
640 KB
sub3_3.txt
WA
76 ms
2040 KB