Submission #3568046


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{
  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){
    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 = 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 100
Code Size 2168 Byte
Status AC
Exec Time 82 ms
Memory 2040 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87: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 15 / 15 35 / 35 50 / 50
Status
AC × 3
AC × 12
AC × 14
AC × 17
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 AC 1 ms 256 KB
sub1_2.txt AC 1 ms 256 KB
sub1_3.txt AC 1 ms 256 KB
sub1_4.txt AC 2 ms 256 KB
sub1_5.txt AC 1 ms 256 KB
sub1_6.txt AC 1 ms 256 KB
sub1_7.txt AC 1 ms 256 KB
sub1_8.txt AC 1 ms 256 KB
sub1_9.txt AC 1 ms 256 KB
sub2_1.txt AC 2 ms 256 KB
sub2_2.txt AC 2 ms 256 KB
sub3_1.txt AC 3 ms 384 KB
sub3_2.txt AC 13 ms 640 KB
sub3_3.txt AC 82 ms 2040 KB