QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648252#1219. 你的名字Lackofgod0 300ms291276kbC++142.7kb2024-10-17 17:56:242024-10-17 17:56:25

Judging History

This is the latest submission verdict.

  • [2024-10-17 17:56:25]
  • Judged
  • Verdict: 0
  • Time: 300ms
  • Memory: 291276kb
Show
  • [2024-10-17 17:56:24]
  • Submitted

answer

#include <bits/stdc++.h>
#define forn(i,aa,bb) for(int i=aa;i<=bb;++i)
#define LL long long 
using namespace std;
const int N=1e6+5;
int ed[N];
int cnt[N],f[N];
vector<int> G[N]; 
string s,t;
struct SAM{
    struct Node{
        int len;
        int link;
        array<int,26> nxt;
        Node():len{},link{},nxt{}{}
    };
    vector<Node> t;
    SAM(){init();}
    void init(){
        t.assign(2,Node());
        t[0].nxt.fill(1);
        t[0].len=-1;
    }
    void clear(){ t.clear(); }
    int newNode() {
        t.emplace_back();
        return t.size()-1;
    }
    int extend(int p,int c) {
        if (t[p].nxt[c] || p==0) {
            int q=t[p].nxt[c];
            if (t[q].len==t[p].len+1) return q;
            int r=newNode();
            t[r].len=t[p].len+1;
            t[r].link=t[q].link;
            t[r].nxt=t[q].nxt;
            t[q].link=r;
            while (t[p].nxt[c]==q) {
                t[p].nxt[c]=r;
                p=t[p].link;
            }
            return r;
        }
        int cur=newNode();
        t[cur].len=t[p].len+1;
        while (!t[p].nxt[c]) {
            t[p].nxt[c]=cur;
            p=t[p].link;
        }
        t[cur].link=extend(p,c);
        cnt[cur]=1;
        return cur;
    }
    int nxt(int p,int x){
        return t[p].nxt[x];
    }
    int link(int p) {
        return t[p].link;
    }
    int len(int p){
        return t[p].len;
    }
    int size(){
        return t.size();
    }
}S,T;
void dfs(int x){
    for(int y:G[x]) {
        dfs(y);
        f[x]=max(f[x],f[y]);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>s;
    int n=s.size();
    int p=1;
    ed[0]=1;
    forn(i,0,n-1)
        p=S.extend(p,s[i]-'a'),ed[i+1]=p;

    int Q;
    cin>>Q;
    while (Q--) {
        T.init();
        int l,r;
        cin>>t>>l>>r;
        int t_len=t.size();
        p=1;
        forn(i,0,t_len-1) 
            p=T.extend(p,t[i]-'a'),ed[i+1]=p;
        p=1;
        int len=0,ans=0;
        forn(i,0,t_len-1) {
            int ch=t[i]-'a';
            if (S.nxt(p,ch)) p=S.nxt(p,ch),len++;
            else {
                while (!S.nxt(p,ch)) p=S.link(p);
                len=S.len(p)+1;
                if (!p) len=0;
                p=S.nxt(p,ch);
            }
            f[ed[i+1]]=max(f[ed[i+1]],len);
        }
        int tot=T.size()-1;
        forn(i,1,tot)
            G[T.link(i)].push_back(i);
        dfs(1);
        forn(i,2,tot) {
            ans+=max(0,T.len(i)-max(f[i],T.len(T.link(i))));
        }
        cout<<ans<<'\n';
        T.clear();
        forn(i,1,tot)
            f[i]=0,G[i].clear();
    }
}
源文件, 语言: C++14

詳細信息


Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 27240kb

input:

aadccabccdcddcdabbbdbdaabcadbcadcccdcadbadaabaaacbacdcdccdcdabbbdbdaadcabdabdbacabdadadbdadbdcddbcbcbaddaaaabccdaddcaaabdbabbcabdbcdccaaddbdcdbbcaccdababdbbdabdcbcccacbddddaacbaccaacadbdbdcabc
190
acdabdbcdcabbacbdacaccbcaddadabccdaabdcdcbcdaadccadcdcaccdcaadcaaddccddbbbadbadbdcaacccdbbbcbdbabcacacb...

output:

18795
19152
18534
18953
17619
17783
17416
18354
17419
18174
18730
19092
18555
18950
17973
18705
17595
17964
17617
18945
17989
17783
17760
18970
18746
18184
17979
18739
18510
18191
17620
18195
17392
17607
17609
18389
18765
19171
17440
18526
17982
17422
18144
18763
17799
17419
19154
18176
18755
17444
...

result:

wrong answer 1st lines differ - expected: '18746', found: '18795'

Test #2:

score: 0
Runtime Error

input:

adbdadddcaddcdaacabadbbbacccaadddcdabaaccbbcbacccbdcdbaabbcbddcdadcabcacccccddbdabbbaacaadcdaddbabcabbbddcdccbaddbbbcdbcabdaaabbdaaadcdacbabccdadbabbdaddcbccddadbdcabcdaabbbabcdacbcaaccabcbaabcbcddcddbbbbaadacbddabbdddabbddbcbdabccbbdacbbdccdbddcdcdcadadbbacbdabbbcddcbadcdddaaabdbbdadddaabbdbaaccdab...

output:

result:

Test #3:

score: 0
Runtime Error

input:

abbabcabadbcbbccbabdcbbacdddcccddadabcadabaadcaddbaaccacaabcbbbcabbbdcbadbaadccdbbdbaaccadbbabdccbcaabbaaccabcbabbcaacbdbbadadbdcbddbbcddcaaacbadabbaacaadddacbadbbddaabbcaccdbdabbcdbbccadccaadabccdaddcabbabadadabdbbadacadcaacbcdccdccaddaacdccbacadaccdbccddacbdcabadbcbbaaccbbabcddccdaabacbcbdbcbdbddb...

output:

result:

Test #4:

score: 0
Wrong Answer
time: 45ms
memory: 27512kb

input:

ddadbccdbdaacdacabdadadcbdbbadddcadbdadddcaddbbacbddddacccccbcabbbdaddcacbbcaaadaaddadadddbadabbadcdbacbdaddadbbbbccdbacaaabcacccdccaaabaddababacdbaccbbbddaabaacadbcddbbcaaccbbbbbdaddaabddbcdbaacbcadbdbccbcbbdacdacbbbcdccadcdbaacbcaadbabadcaccabdddacacabdbcdadccaddcdcaaabcacccbdbdadcbdcabddabbdabdcd...

output:

2894736
2991677
2979416
3050694
2815907
3097754
2950205
2865867
2830125
2947853
2811101
3068017
3030926
2892295
2861118
2977069
3070557
3023668
3023555
2913855
2913848
2825350
2825345
2923615
2880233
2991740
3028521
3072878
2925975
2957449
2837289
3026097
3036010
3033452
2996615
2994201
3043288
2964...

result:

wrong answer 1st lines differ - expected: '2894585', found: '2894736'

Test #5:

score: 0
Runtime Error

input:

bacccaaabdacddbbabdabccbdabddccdbcdcdbdbccbddbbcaaddaacdcaaadcbcaddbabbaddaaaddaaccdcaccacababccaddaccbcacbbdccabaacacdcbccbdbadcdbbbbacacdcbbbbaadbcbaadbcadadbbddbccaadbdbcbabdaacdcdacdbcdbdccdabbacbddabcabccbbabcddbdddcaabbcaddbbdabcaddbbcaadabcbdcabcacdaabbdddadaacbbccdbccdabbdcaddddcccdaaaaddada...

output:

result:

Test #6:

score: 0
Wrong Answer
time: 300ms
memory: 291276kb

input:

jmoifvagmonbuxznpdxtcgfycygerridhihasxonifvcorwbbadpyjvgyveicsfcrcjjecfktxuumtvfjxocbgeoeefrzlykfqeaarrlhkjovevehnezlcjikjjjfuxfoclvirrbctlicoitgwnphfzgzepxyejlsijruxxdvzahqjpaqhgcumtjnwkbskyengdgzbtxteacjoyvndwiturrdtlcyccbckhmlfyqohfcjvzhtcuqxxpexkvlckohvidmwkghiijakocqyjskcfoxxzffzgtylbiyythobvdx...

output:

309448711

result:

wrong answer 1st lines differ - expected: '124863337763', found: '309448711'

Test #7:

score: 0
Runtime Error

input:

jxfsgnlqidcnbfleihizzderbbyzminbutjjknmojrymnghyunksfsqtfijisxyxfaygactkupfrpnugcrvhseqxpdiyrzrzanctqtygvhpumvlxwmvduwbysmkzpckcgbjxmlgyfhdpdjqehloisnpilhpshexuljbjlnkcbkjcnpudmycjigdirokeyvcvkmkrsyjbftizewmcfyuxghxqmwmqdvhswdnsjvybvefdnupdkrqcvnlnfbybifdovvapsdjoppvzvkmxjzevqifzclignjponvndafghncmm...

output:

result:

Test #8:

score: 0
Runtime Error

input:

lbmckmhibhhmgglmcbfkclhacldibgaadakchjabmimjlidhhldljfmkegaieahdbjccdhjefbfebedjiefeflbejkihgjbfgeflchegbamekdlaaacfgabdabmfgjgfmjailbdgbhfbmaaclcidkkgldmejjhcmahhmgkimgfclcgkkalgdcmaiieakmkmflhbdmmibkbkfcjieekbccheahgegkfchfchemgkfghmiabllamichbbdbhjlcfafkijgihgmekhkdebkfbkdagdbhcgjmkamlfhmkjgmfafl...

output:

result:

Test #9:

score: 0
Wrong Answer
time: 35ms
memory: 48248kb

input:

uwhchfeaycdqlasqdrbylqxaridtgcmyrmkdfdahthdwvkojhqxacqomockaqqoanitzhkmcgcdvniteghvxiyjrqziqjiuljewrdwaabtqwfrfalgloikpxcllbngrzphwcsdmiflqvznvuvxivxsvpqfgkefowexaoplhqfenuwawvwhtmocrmqifqdbyudhmkgiucudnxbjaucppbzobxpmqufhvexdvyjiefmxlfpczvqiuqucvnryxicvusurdiaavudphnnmfqgtichpwfvpaglqqzlmbwwwjohdgx...

output:

199945557
2
3
2
3
3
1
3
3
3
2
3
3
3
3
3
3
3
3
3
2
3
3
3
3
3
2
3
2
2
3
2
3
2
2
2
3
2
3
2
2
2
3
2
1
3
3
3
1
3
3
2
3
2
3
2
3
2
2
3
2
3
3
2
1
3
2
3
3
2
3
3
1
3
3
3
3
2
2
3
2
3
0
3
2
3
2
3
3
3
3
3
2
3
0
3
3
3
2
3
2
3
3
3
3
2
3
3
3
2
3
3
3
3
3
3
3
2
3
2
1
3
3
3
2
2
3
2
3
3
3
3
3
3
3
2
3
2
3
2
3
2
2
2
4
2
...

result:

wrong answer 1st lines differ - expected: '199945526', found: '199945557'

Test #10:

score: 0
Runtime Error

input:

kimblfhedhamehaaacifgbgflkkldkalaakkhlaiejmeccmcffablhblmggjdmkbhljkkhgfjklieakmkjaamgikmccfkfghljahlkijgjdaechcbifailjcglkkedlgicjebfhiebkfciljkeacceejmkaalhcajfhfmkcecdklbdajdlfikkhiekdbebjbbdfgjcjhfbkclbhbbhjfdffegebkjfkcdilemclilbhflaihgihcgkldcbaakhdjhbekibbigibjdmjbbfalhccmddmckgljfmhgjbalbdjg...

output:

result:

Test #11:

score: 0
Runtime Error

input:

hpfxngoxndlosbzylksgzehfhkodfvqwwbtwlreetgeusomoymlaukhqqeqhfawfvuqjbwyrtwwjzmrtrnhvibtibiachlutcqbsydmynzxzdrkydyyekbmezwhvvfngnlklzdjpgbpjatahwuvoluqjoefktvlwdtynwprfekbpvgqtwmwneaofpktxfudwpibhlqmiybqbvsfsywlbktjcqvzwxtddkmliwukvkqsdssszsbmtnpynoohpgclvufblcdvqwrpjtuayinwqppbuidyynbpaolisqodbrqqt...

output:

result:

Test #12:

score: 0
Runtime Error

input:

cdfmjmimggmlmabjlakafafdgkbdkaclfemhajdamjkliajhmajfidkghmejelfkjedddkcgbdidelhghbabckiihdjhdjhakmeldjbikdagdfhalfikeggefcmehhgccilmaehhkagafafaegjgakjekcbhbbjgfhimhmlblgmeddfffdhfgmiacadfhglhjaekdaeacdbfmlcjfffbkcbffljjkbhigejmmmhkaljcljibgekjfhefmbjilcahefblblgeledddgemdgihfecclicgbkmilmifflllhmmc...

output:

result:

Test #13:

score: 0
Runtime Error

input:

ophmmxojwyabxitozutwdxkmleazyhkqzfhqtdjggpjclzkhcerzmpdkprqjkmnpvccyajlwcohqgzqticihosjhxmwymdzoqnawgmtegjqyrngnqcheacmkgbrwsfldsmlnqjkocblhrnwguaexvnfvrceexfqpzumxsuuhfhdhujqoqdxrkknnhiygrabiqspaqdqreiswbcqdjnyqijdzolltfiiismxltjukwuixllitlyjglwwqekrlbkbwutvnifampunpzmpmwyclwxwgrowvnbqqmkreqhrwgvey...

output:

result:

Test #14:

score: 0
Runtime Error

input:

lbmafbiicbjcmhbbmbabkgmbafmmhjldiifkmhejgmdcbijilcaidajjjebklkikjdjefalfkemjmbifalacllkcehbgkdkabiiefmhjcimlmckcbebidhddclhhlabdalegkfhcdbejbdmbhbfgelmkfdbkbdaclahbfggijmbgigilebmbijddfkjbafdjghijiibljgclgbciijhmjdhcjelmhiecaiahkhledfbekdlmcdceecckhkebclhilgbikmfgjmjgflmffkdjjkbcaemagedmcjajgikgefga...

output:

result:

Test #15:

score: 0
Runtime Error

input:

dsppfaesydhozppylwmfzcvsllhggovukeeepvtiodzzdcmlauhymvxijszrobdecuhxjsivtwjtmvphssgvyifmixgddeuofabohugyfnnqbtsjrynkvtvcqkrhwovooktcfwmxagrxgekxdgldaqffybwmdkeykyocudevwdojhcbhipfwclhzmtoyznnbdadomffoaxihkuojezabjppeyzkgwjgcpvuuxvojahfrdeybcklvqwvfftcwkxqfhbddbxfduvitycznkuzgukryyhktzoslzqiiggugpwvr...

output:

result:

Test #16:

score: 0
Runtime Error

input:

lgcjmilcjkfljihhadhcgcljecggdihjjihgdmbgggmdmfligahflfffcbcmfjlfmamfmcllfgffcciihhcfdihlbgbklmkjacjkhjajhaijifebillabigdeichhklajlechjhbeaiahhidemiaaaehkkaelabbdchficchchdcljbbbdmjfldkmjledjkkhldjjagdimadbdkkmcblkgfbmghieiiaamicjlemabecdemjbbhjjadfhlbaaglbfbbbilljmfjmadcmckfegfalkacbkjkafcgaklgabjkm...

output:

result:

Test #17:

score: 0
Runtime Error

input:

crouxgkvirnjrytirundlljrgfwtazivrwzxxwditbfcooymmlaqvtisxnwbhhdusjrqtvebvgmuaietaotldzzsrqtplqfucfyjpfrohwraeeufvpetorvakablkyvvnwetsrqjlxhmjwgqekapdrvcymvxdzojvbsvcjqrjsdnimathoxcldskndebsfnoqpwxjiicaqdaxhmfnozvwhezimqwnwaoktflkfpdqyhuwtdtgqanymowveuxayebwbjeliulrglhaxwgmgvgiqwqvrkwetmdvkshxwpobakc...

output:

result:

Test #18:

score: 0
Runtime Error

input:

hlheiljjdhhlgihkakdbmjjkjbihblhabaaafedcjickgbmimhldcfdgaeaemhheclgeglffkkiklgalagllffkjkkjbkllkgkkbblficjmklljcfallcicmfdflgebfjeacjejeedmimfdeiadbegfkckiaffagigmckdkihdikgilgehmaglhiddljghmfhgikfkgmfkadekgfalhlemfkdeggcdfkhmjdcdabmeebblbgeflbhkcjgdgadlbfmdebkhhhfajjiflejijamgjekelmjhcmakcglmhafdai...

output:

result:

Test #19:

score: 0
Runtime Error

input:

hcickbjbggigfjddcmijgfbafdebdkcldbibaaegkhmdeibkjdjigbmfelkbdablaccmeblcgikdglmllmdagaaaikfjhdcldhmhmiiiccbhehdhbkjdgkkjhfkflckidfibicfihaagficicjkbiiejddegmcahacchfgmkmmlehbelhlmbkamelfjhkmgfljbaffjjfmfhmhafjhhhdlgfggbilkkcghfaalllcdeffbbjichaiedagaalehkcaglcacgldciahdgehibefmghedciddglfbbmdigdbjij...

output:

result:

Test #20:

score: 0
Runtime Error

input:

cjhkkbhdfmbagemlcmcdclghhcebjlaikgbdlbkedeckmimkeffkjfljmghahfgeihehlfhicjckhjmidafdkhfgehjdgdclckchjddkglaijcfcmigkgmhkmggelagbkbkikaghbadbfeifkemehhcljcfjeljejeehbklflekflaedfeclhidaahikdfaeljbhbaffkdblmecidjglkddkmecifgccmjkjhjecgaklmemfcfemlfmbkljjbakdhchehfhaelhgkicdbhgddcfjeikimklccbdmccjiilhf...

output:

result:

Test #21:

score: 0
Runtime Error

input:

acdalbjachemiccjijekjladlmgcdibegjemfggmcajmkdfaicklclhhjjiifdjkglcdieahidalajicmabkejeggmjdacmljghlicficlaidacjegkhgdmalfbgakblgfbglebhjmkccfgkdkcbgddfgcmkkddlmlikljhmcgfddgkfhddkiekkaefbedjhglclfgebfddlbkkadhlahccmbgjagkkchemmhgbcjkcjdgbmbfhmhgckffedkkllkemkegjhbkijhkjmckkgcccebelfdikbfeigdflebkck...

output:

result:

Test #22:

score: 0
Runtime Error

input:

mddlmgjdadiajebkkjdcfcaemmacbeefbiheblhihlahcilkgcgcgbgbkdddbiedlejkaibalfggglkghmddiiikfabgmggecdmifaegcmkfcmlcfhlecifdiejflclehcbajacmakchcekkiddljfdlejgefbgkgicbdjamafjfgcdmhaejffmdaedaidabihdckhjdkfdclaafcibjfidakllflmejfaeeilaehkicmifjcdiagiihchgefafeaabbihmkddcaembjgjdeljjldagjgghammkfagahdjgb...

output:

result:

Test #23:

score: 0
Runtime Error

input:

llfdgmcekbmbimkccddilecgmlimhkklijdgcfjcdkblbglbaaegedfeihjfgigigfbajgakjmmafechejfihfmdkidmlfdcejkkielgcakckilmlgiklmlalklfdcgkhlmlhkjbkhmdkbhmbfidfmccicgcbejmklcmelcigfjjiaifebbdimekgaglhejaadaglhahfkmkljkfakaifihfihikecehmafbgicelabajgghlmffhgfciclmhmbfhbkbbffmikkeadafebkjkdcidbgadmiaelbhkegimmbf...

output:

result:

Test #24:

score: 0
Runtime Error

input:

dhblhcfekgfmbjkhalldhjckleeffihfallgiafelkkehflcmbikdiijmajkeaghlddammajjdffieiidbgedfekciajfflgbgegmfmaljamaliihmjladahiglmkafmiiflcbhbhceimhmhheeidaejgaecmahcmchclijjdjajmkjgjdgkhmljmjlgadflbdkdkgbggdddicllcfkdmajigmglkfcllijleblcaabkajjghhdgkdbllmjhahjecccfhcgmfemljbkamhgbehjkfffaickeagejjhkgmimb...

output:

result:

Test #25:

score: 0
Runtime Error

input:

iiafeelfecahcjmkadhjkdmmelhmaiafglhiabmlafgmackbbkgfdhdhlageljhmlmehhjgbgkjmbaiffjhcfceiidghmggkhlhkcjdjiehfdcjdlkblgbkcdahgiccjiimggkdlhlkgddbiigbjhbdblbggaealbkldjbfdecmcijdfajlgccfbldbkjmbcmkklfmjfblbhieibecfgjcbchkegbdamflhfjfdgjglkakkgheakegkhlllmhljekmidlhfcmjlgmmajmgjmmlfkhhbklgliejcikjehdijd...

output:

result:
English 繁體中文 简体中文

伺服器時間: 2025-02-08 23:55:52 | 開源專案