이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define FOD(i,a,b) for (int i=(a);i>=(b);i--)
#define bit(x,y) ((x)>>(y))&1
#define pb push_back
#define ll long long
#define ii pair < int,int >
#define f first
#define s second
#define M 1000000007
#define N 100005
using namespace std;
int n,m;
string S[N];
struct iii {
string p,q;
int id;
} T[N];
int cnt=0;
int Trie[2000005][4],Min[2000005],Max[2000005],End[2000005];
void Add(string s,int id) {
int u=0;
for (auto c : s) {
int x=0;
if (c=='U') x=1;
else
if (c=='A') x=2;
else
if (c=='C') x=3;
if (!Trie[u][c]) Trie[u][c]=++cnt;
u=Trie[u][c];
if (!Min[u]) Min[u]=id;
Max[u]=id;
}
}
ii Get(string s) {
int u=0;
for (auto c : s) {
int x=0;
if (c=='U') x=1;
else
if (c=='A') x=2;
else
if (c=='C') x=3;
if (!Trie[u][c]) return {0,0};
u=Trie[u][c];
}
return {Min[u],Max[u]};
}
vector < int > adj[N];
int ans[N];
void Add2(string s) {
int u=0;
for (auto c : s) {
int x=0;
if (c=='U') x=1;
else
if (c=='A') x=2;
else
if (c=='C') x=3;
if (!Trie[u][c]) Trie[u][c]=++cnt;
u=Trie[u][c];
++End[u];
}
}
int Get2(string s) {
int u=0;
for (auto c : s) {
int x=0;
if (c=='U') x=1;
else
if (c=='A') x=2;
else
if (c=='C') x=3;
if (!Trie[u][c]) return 0;
u=Trie[u][c];
}
return End[u];
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
FOR(i,1,n) cin>>S[i];
sort(S+1,S+n+1);
FOR(i,1,n) Add(S[i],i);
FOR(i,1,m) {
cin>>T[i].p>>T[i].q;
reverse(T[i].q.begin(),T[i].q.end());
ii tmp=Get(T[i].p);
int l=tmp.f,r=tmp.s;
if (l && r && l<=r) {
adj[l-1].pb(-i);
adj[r].pb(i);
}
//cout<<l<<" "<<r<<'\n';
}
memset(Trie,0,sizeof(Trie));
FOR(i,1,n) {
reverse(S[i].begin(),S[i].end());
Add2(S[i]);
//cout<<S[i]<<'\n';
for (auto j : adj[i]) {
int id=abs(j);
int val=Get2(T[id].q);
if (j<0) ans[id]-=val;
else ans[id]+=val;
//if (id==2) cout<<T[id].q<<" "<<val<<'\n';
}
}
FOR(i,1,m) cout<<ans[i]<<'\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
selling_rna.cpp: In function 'void Add(std::string, long long int)':
selling_rna.cpp:31:22: warning: array subscript has type 'char' [-Wchar-subscripts]
31 | if (!Trie[u][c]) Trie[u][c]=++cnt;
| ^
selling_rna.cpp:31:34: warning: array subscript has type 'char' [-Wchar-subscripts]
31 | if (!Trie[u][c]) Trie[u][c]=++cnt;
| ^
selling_rna.cpp:32:19: warning: array subscript has type 'char' [-Wchar-subscripts]
32 | u=Trie[u][c];
| ^
selling_rna.cpp:25:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
25 | int x=0;
| ^
selling_rna.cpp: In function 'std::pair<long long int, long long int> Get(std::string)':
selling_rna.cpp:46:22: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | if (!Trie[u][c]) return {0,0};
| ^
selling_rna.cpp:47:19: warning: array subscript has type 'char' [-Wchar-subscripts]
47 | u=Trie[u][c];
| ^
selling_rna.cpp:40:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
40 | int x=0;
| ^
selling_rna.cpp: In function 'void Add2(std::string)':
selling_rna.cpp:62:22: warning: array subscript has type 'char' [-Wchar-subscripts]
62 | if (!Trie[u][c]) Trie[u][c]=++cnt;
| ^
selling_rna.cpp:62:34: warning: array subscript has type 'char' [-Wchar-subscripts]
62 | if (!Trie[u][c]) Trie[u][c]=++cnt;
| ^
selling_rna.cpp:63:19: warning: array subscript has type 'char' [-Wchar-subscripts]
63 | u=Trie[u][c];
| ^
selling_rna.cpp:56:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
56 | int x=0;
| ^
selling_rna.cpp: In function 'long long int Get2(std::string)':
selling_rna.cpp:76:22: warning: array subscript has type 'char' [-Wchar-subscripts]
76 | if (!Trie[u][c]) return 0;
| ^
selling_rna.cpp:77:19: warning: array subscript has type 'char' [-Wchar-subscripts]
77 | u=Trie[u][c];
| ^
selling_rna.cpp:70:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
70 | int x=0;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |