Submission #1353412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1353412		dhuyyyy	Selling RNA Strands (JOI16_selling_rna)	C++20	Compilation error	0 ms	0 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(s) s.begin(),s.end()
#define sz(s) (int)s.size()

using namespace std;

using ll = long long;
using ii = pair<int,int>;
using aa = array<int,3>;

const int N = 2e6+5;
const int blocks = 500;
const int INF = 1e18;
const int MOD = 1e9+7;

int n, q, timer = 0;

int trie[N * 30][5];

string s[N];

vector <int> bitsuf[N], bitpre[N];

string s1, s2;

int get(char c){
    if (c == 'A') return 0;
    if (c == 'U') return 1;
    if (c == 'G') return 2;
    if (c == 'C') return 3;
}

void addpre(string &s, int i){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!trie[node][val]) trie[node][val] = ++timer;
        node = trie[node][val];
        bitpre[node].push_back(i);
    }
}

void addsuf(string &s,int i){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!trie[node][val]) trie[node][val] = ++timer;
        node = trie[node][val];
        bitsuf[node].push_back(i);
    }
}

ii getpre(string &s){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!trie[node][val]) return {-1,-1};
        node = trie[node][val];
    }
    return {bitpre[node][0],bitpre[node].back()};
}

int getsuf(string &s,int l,int r){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!trie[node][val]) return 0;
        node = trie[node][val];
    }
    int k = upper_bound(all(bitsuf[node]),r) - bitsuf[node].begin();
    int j = lower_bound(all(bitsuf[node]),l) - bitsuf[node].begin();
    return k - j;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    #define name "main"
    if (fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> s[i];
    sort(s+1,s+1+n);
    for (int i = 1; i <= n; i++){
        addpre(s[i],i);
        reverse(all(s[i]));
        addsuf(s[i],i);
    }
    while (q--){
        cin >> s1 >> s2;
        ii res = getpre(s1);
        if (res.fi == -1) cout << 0 << '\n';
        else{
            reverse(all(s2));
            cout << getsuf(s2,res.fi,res.se) << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'long long int get(char)':
selling_rna.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1f): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x66): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x71): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x7c): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa0): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xab): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xc8): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xe1): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xf4): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cin_sync' defined in .bss._ZN14__gnu_internal12buf_cin_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xfb): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x101): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1ed): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x252): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2bc): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x316): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x50f): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x57d): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f0): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x654): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status