QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647909#1219. 你的名字Lackofgod0 70ms124740kbC++142.2kb2024-10-17 16:09:362024-10-17 16:09:37

Judging History

This is the latest submission verdict.

  • [2024-10-17 16:09:37]
  • Judged
  • Verdict: 0
  • Time: 70ms
  • Memory: 124740kb
Show
  • [2024-10-17 16:09:36]
  • 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=2e6+5;
int ed[N];
int cnt[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;
    }
    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;
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--) {
        int l,r;
        cin>>t>>l>>r;
        if (l==1 && r==n) cout<<"1\n";
        int p=1;
        int ans=0,len=0;
        int ii=0;
        for(char &x:t) {
            ii++;
            if (S.nxt(p,x-'a')) len++,p=S.nxt(p,x-'a');
            else {
                while (!S.nxt(p,x-'a')) p=S.link(p);
                len=S.len(p)+1;
                if (!p) len=0;
                p=S.nxt(p,x-'a');
            } 
            ans+=ii-len;
        }
        cout<<ans<<'\n';
    }
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5720kb

input:

aadccabccdcddcdabbbdbdaabcadbcadcccdcadbadaabaaacbacdcdccdcdabbbdbdaadcabdabdbacabdadadbdadbdcddbcbcbaddaaaabccdaddcaaabdbabbcabdbcdccaaddbdcdbbcaccdababdbbdabdcbcccacbddddaacbaccaacadbdbdcabc
190
acdabdbcdcabbacbdacaccbcaddadabccdaabdcdcbcdaadccadcdcaccdcaadcaaddccddbbbadbadbdcaacccdbbbcbdbabcacacb...

output:

1
18858
1
19235
1
18586
1
19032
1
17716
1
17826
1
17487
1
18439
1
17495
1
18251
1
18794
1
19206
1
18623
1
19022
1
18041
1
18795
1
17682
1
18033
1
17667
1
19014
1
18058
1
17839
1
17822
1
19064
1
18855
1
18246
1
18049
1
18805
1
18620
1
18280
1
17718
1
18256
1
17469
1
17685
1
17704
1
18469
1
18855
1
19...

result:

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

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: 7ms
memory: 6064kb

input:

ddadbccdbdaacdacabdadadcbdbbadddcadbdadddcaddbbacbddddacccccbcabbbdaddcacbbcaaadaaddadadddbadabbadcdbacbdaddadbbbbccdbacaaabcacccdccaaabaddababacdbaccbbbddaabaacadbcddbbcaaccbbbbbdaddaabddbcdbaacbcadbdbccbcbbdacdacbbbcdccadcdbaacbcaadbabadcaccabdddacacabdbcdadccaddcdcaaabcacccbdbdadcbdcabddabbdabdcd...

output:

1
2896146
1
2993224
1
2980847
1
3052248
1
2817319
1
3099385
1
2951605
1
2867317
1
2831470
1
2949382
1
2812469
1
3069441
1
3032447
1
2893828
1
2862509
1
2978556
1
3072030
1
3025133
1
3025101
1
2915342
1
2915456
1
2826775
1
2826681
1
2925020
1
2881790
1
2993215
1
3030041
1
3074326
1
2927486
1
2958910
...

result:

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

Test #5:

score: 0
Runtime Error

input:

bacccaaabdacddbbabdabccbdabddccdbcdcdbdbccbddbbcaaddaacdcaaadcbcaddbabbaddaaaddaaccdcaccacababccaddaccbcacbbdccabaacacdcbccbdbadcdbbbbacacdcbbbbaadbcbaadbcadadbbddbccaadbdbcbabdaacdcdacdbcdbdccdabbacbddabcabccbbabcddbdddcaabbcaddbbdabcaddbbcaadabcbdcabcacdaabbdddadaacbbccdbccdabbdcaddddcccdaaaaddada...

output:

result:

Test #6:

score: 0
Wrong Answer
time: 70ms
memory: 124740kb

input:

jmoifvagmonbuxznpdxtcgfycygerridhihasxonifvcorwbbadpyjvgyveicsfcrcjjecfktxuumtvfjxocbgeoeefrzlykfqeaarrlhkjovevehnezlcjikjjjfuxfoclvirrbctlicoitgwnphfzgzepxyejlsijruxxdvzahqjpaqhgcumtjnwkbskyengdgzbtxteacjoyvndwiturrdtlcyccbckhmlfyqohfcjvzhtcuqxxpexkvlckohvidmwkghiijakocqyjskcfoxxzffzgtylbiyythobvdx...

output:

1
309936564

result:

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

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: 18ms
memory: 21528kb

input:

uwhchfeaycdqlasqdrbylqxaridtgcmyrmkdfdahthdwvkojhqxacqomockaqqoanitzhkmcgcdvniteghvxiyjrqziqjiuljewrdwaabtqwfrfalgloikpxcllbngrzphwcsdmiflqvznvuvxivxsvpqfgkefowexaoplhqfenuwawvwhtmocrmqifqdbyudhmkgiucudnxbjaucppbzobxpmqufhvexdvyjiefmxlfpczvqiuqucvnryxicvusurdiaavudphnnmfqgtichpwfvpaglqqzlmbwwwjohdgx...

output:

1
199945995
1
2
1
3
1
2
1
3
1
3
1
1
1
3
1
3
1
3
1
2
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
2
1
3
1
3
1
3
1
3
1
3
1
2
1
3
1
2
1
2
1
3
1
2
1
3
1
2
1
2
1
2
1
3
1
2
1
3
1
2
1
2
1
2
1
3
1
2
1
1
1
3
1
3
1
3
1
1
1
3
1
3
1
2
1
3
1
2
1
3
1
2
1
3
1
2
1
2
1
3
1
2
1
3
1
3
1
2
1
1
1
3
1
2
1
3
1
3
1
2
1
3
1
3
1
1
...

result:

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

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 繁體中文 简体中文

Server Time: 2025-02-08 21:04:42 | OpenSource Project