QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#647901	#1219. 你的名字	Lackofgod	0	67ms	125440kb	C++14	2.1kb	2024-10-17 16:07:06	2024-10-17 16:07:08

Judging History

This is the latest submission verdict.

[2024-10-17 16:07:08]
Judged

Verdict: 0
Time: 67ms
Memory: 125440kb

Show

[2024-10-17 16:07:06]
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;
        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';
    }
}

源文件, 语言: C++14

详细

Pretests

Final Tests

Test #1:

score: 0

Wrong Answer

time: 1ms

memory: 5672kb

input:

aadccabccdcddcdabbbdbdaabcadbcadcccdcadbadaabaaacbacdcdccdcdabbbdbdaadcabdabdbacabdadadbdadbdcddbcbcbaddaaaabccdaddcaaabdbabbcabdbcdccaaddbdcdbbcaccdababdbbdabdcbcccacbddddaacbaccaacadbdbdcabc
190
acdabdbcdcabbacbdacaccbcaddadabccdaabdcdcbcdaadccadcdcaccdcaadcaaddccddbbbadbadbdcaacccdbbbcbdbabcacacb...

output:

result:

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

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: 5800kb

input:

ddadbccdbdaacdacabdadadcbdbbadddcadbdadddcaddbbacbddddacccccbcabbbdaddcacbbcaaadaaddadadddbadabbadcdbacbdaddadbbbbccdbacaaabcacccdccaaabaddababacdbaccbbbddaabaacadbcddbbcaaccbbbbbdaddaabddbcdbaacbcadbdbccbcbbdacdacbbbcdccadcdbaacbcaadbabadcaccabdddacacabdbcdadccaddcdcaaabcacccbdbdadcbdcabddabbdabdcd...

output:

result:

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

Test #5:

score: 0

Runtime Error

input:

bacccaaabdacddbbabdabccbdabddccdbcdcdbdbccbddbbcaaddaacdcaaadcbcaddbabbaddaaaddaaccdcaccacababccaddaccbcacbbdccabaacacdcbccbdbadcdbbbbacacdcbbbbaadbcbaadbcadadbbddbccaadbdbcbabdaacdcdacdbcdbdccdabbacbddabcabccbbabcddbdddcaabbcaddbbdabcaddbbcaadabcbdcabcacdaabbdddadaacbbccdbccdabbdcaddddcccdaaaaddada...

output:

result:

Test #6:

score: 0

Wrong Answer

time: 67ms

memory: 125440kb

input:

jmoifvagmonbuxznpdxtcgfycygerridhihasxonifvcorwbbadpyjvgyveicsfcrcjjecfktxuumtvfjxocbgeoeefrzlykfqeaarrlhkjovevehnezlcjikjjjfuxfoclvirrbctlicoitgwnphfzgzepxyejlsijruxxdvzahqjpaqhgcumtjnwkbskyengdgzbtxteacjoyvndwiturrdtlcyccbckhmlfyqohfcjvzhtcuqxxpexkvlckohvidmwkghiijakocqyjskcfoxxzffzgtylbiyythobvdx...

output:

309936564

result:

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

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: 11ms

memory: 21172kb

input:

uwhchfeaycdqlasqdrbylqxaridtgcmyrmkdfdahthdwvkojhqxacqomockaqqoanitzhkmcgcdvniteghvxiyjrqziqjiuljewrdwaabtqwfrfalgloikpxcllbngrzphwcsdmiflqvznvuvxivxsvpqfgkefowexaoplhqfenuwawvwhtmocrmqifqdbyudhmkgiucudnxbjaucppbzobxpmqufhvexdvyjiefmxlfpczvqiuqucvnryxicvusurdiaavudphnnmfqgtichpwfvpaglqqzlmbwwwjohdgx...

output:

result:

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

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...