Submission #1722036
Source Code Expand
#include <bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define ep emplace
#define MOD 1000000007LL
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define for1(i, n) for(int i = 1; i <= int(n); i++)
#define ford(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define fore(i, a, b) for(int i = int(a); i <= int(b); i++)
#define debug(x) cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
const ll oo = 1000000000000000000LL;
const int N = 1000006;
int n;
char s[N], f[N];
int sa[N], lcp[N], p[N], L[N], R[N];
pair<int, int> r[N];
void sort(){
sort(sa, sa+n, [=](const int &a, const int &b){
return r[a] < r[b];
});
}
void build_sa(){
forn(i, n) sa[i] = i, r[i].ff = s[i], r[i].ss = 0;
sort();
for(int sz = 1; sz < n; sz *= 2){
pair<int, int> last = r[ sa[0] ];
r[ sa[0] ].ff = 0;
for1(i, n-1){
if(r[ sa[i] ] == last) r[ sa[i] ].ff = r[ sa[i-1] ].ff;
else{
last = r[ sa[i] ];
r[ sa[i] ].ff = r[ sa[i-1] ].ff+1;
}
}
forn(i, n){
if(sa[i] + sz < n) r[ sa[i] ].ss = r[ sa[i]+sz ].ff;
else r[ sa[i] ].ss = -1;
}
sort();
}
}
// lcp[i] = lcp(s[:i], s[:i+1])
void build_lcp(){
int k = 0;
forn(i, n) r[ sa[i] ].ff = i;
for(int i = 0; i < n; i++, k ? k-- : 0){
if(r[i].ff == n-1) k = 0;
else{
int j = sa[r[i].ff+1];
while(i+k < n && j+k < n && s[i+k] == s[j+k]) k++;
}
lcp[r[i].ff] = k;
}
}
int main(){
scanf("%s", s);
n = strlen(s);
build_sa(), build_lcp();
ll ans = 0;
forn(i, n) ans += (n - sa[i]) - lcp[i];
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time
2017-10-28 23:20:24+0900
Task
E - 部分文字列
User
Nson
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2004 Byte
Status
WA
Exec Time
78 ms
Memory
7168 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:76:23: 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
WA
2 ms
6400 KB
sample_2.txt
WA
2 ms
6400 KB
sample_3.txt
WA
2 ms
6400 KB
sub1_1.txt
WA
2 ms
6400 KB
sub1_2.txt
WA
2 ms
6400 KB
sub1_3.txt
WA
2 ms
6400 KB
sub1_4.txt
WA
2 ms
6400 KB
sub1_5.txt
WA
2 ms
6400 KB
sub1_6.txt
WA
2 ms
6400 KB
sub1_7.txt
WA
2 ms
6400 KB
sub1_8.txt
WA
2 ms
6400 KB
sub1_9.txt
WA
2 ms
6400 KB
sub2_1.txt
WA
2 ms
6400 KB
sub2_2.txt
WA
2 ms
6400 KB
sub3_1.txt
WA
4 ms
6400 KB
sub3_2.txt
WA
12 ms
6528 KB
sub3_3.txt
WA
78 ms
7168 KB