제출 #1070447

#제출 시각아이디문제언어결과실행 시간메모리
1070447sitablechairSelling RNA Strands (JOI16_selling_rna)C++17
35 / 100
147 ms181192 KiB
#include <bits/stdc++.h> #define ll long long #define ldb long double #define endl '\n' #define For(i,l,r) for(int i=l;i<=r;i++) #define ForD(i,r,l) for(int i=r;i>=l;i--) #define REP(i,l,r) For(i,l,r-1) #define PER(i,r,l) ForD(i,r-1,l) #define ff first #define ss second #define pb emplace_back #define all(x) x.begin(),x.end() #define All(x,n) x+1,x+1+n #define Alll(x,n) x,x+n #define sz(x) (signed)x.size() #define unq(x) x.resize(unique(all(x))-x.begin()) #define mpa make_pair #ifdef NCGM #include"debug.h" #else #define debug(...) "fr"; #endif using namespace std; const int N=5e5+9; int id[500]; struct Trie{ struct Node{ int child[22]; int exist, cnt; int mini=-1; } nodes[N]; int cur; Trie() : cur(0) { memset(nodes[0].child, -1, sizeof(nodes[cur].child)); nodes[0].exist = nodes[0].cnt = 0; }; int newn() { cur++; memset(nodes[cur].child, -1, sizeof(nodes[cur].child)); nodes[cur].exist = nodes[cur].cnt = 0; return cur; } void add(string s,int ind=0) { int pos = 0; for (auto f : s) { int c = id[f]; if (nodes[pos].child[c] == -1) { nodes[pos].child[c] = newn(); } pos = nodes[pos].child[c]; nodes[pos].cnt++; if (ind) { if (nodes[pos].mini==-1) nodes[pos].mini=ind; else nodes[pos].mini=min(nodes[pos].mini,ind); } } nodes[pos].exist++; } bool delHandle(int pos, string& s, int i) { if (i != (int)s.size()) { int c = id[s[i]]; bool isChildDeleted = delHandle(nodes[pos].child[c], s, i + 1); if (isChildDeleted) nodes[pos].child[c] = -1; } else nodes[pos].exist--; if (pos != 0) { nodes[pos].cnt--; if (nodes[pos].cnt == 0) return true; } return false; } void del(string &s) { if (find(s) == false) return; delHandle(0, s, 0); } bool find(string &s) { int pos = 0; for (auto f : s) { int c = id[f]; if (nodes[pos].child[c] == -1) return false; pos = nodes[pos].child[c]; } return (nodes[pos].exist != 0); } pair<int,int> get(string &s) { int pos=0; for(auto f: s) { int c=id[f]; if (nodes[pos].child[c]==-1) return mpa(-1,-1); pos=nodes[pos].child[c]; } return mpa(nodes[pos].mini,nodes[pos].mini+nodes[pos].cnt-1); } int getnum(string &s) { int pos=0; for(auto f: s) { int c=id[f]; if (nodes[pos].child[c]==-1) return 0; pos=nodes[pos].child[c]; } return nodes[pos].cnt; } }; ll hilOrd(int x, int y, int pow, int rotate) { if (x<0 || y<0) return 1e17; if (pow == 0) return 0; int hpow = 1 << (pow-1); int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2); seg = (seg + rotate) & 3; const int rotateDelta[4] = {3, 0, 0, 1}; int nx = x & (x ^ hpow), ny = y & (y ^ hpow); int nrot = (rotate + rotateDelta[seg]) & 3; ll subSquareSize = int64_t(1) << (2*pow - 2); ll ans = seg * subSquareSize; ll add = hilOrd(nx, ny, pow-1, nrot); ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1); return ans; } struct query { int l,r,ind; ll order=0; string p,q; void calOrd() { order=hilOrd(l,r,21,0); } }; Trie trie,trie1; query qr[N]; string s[N],s1[N]; int n,m,ans[N]; int main() { cin.tie(0)->sync_with_stdio(0); id['C']=4,id['U']=1,id['G']=2,id['A']=3; cin >> n >> m; For(i,1,n) cin >> s[i]; sort(s,s+1+n); For(i,1,n) { s1[i]=s[i]; reverse(all(s1[i])); } For(i,1,n) trie.add(s[i],i); For(i,1,m) { cin >> qr[i].p >> qr[i].q; reverse(all(qr[i].q)); qr[i].ind=i; pair<int,int> sus=trie.get(qr[i].p); qr[i].l=sus.ff; qr[i].r=sus.ss; qr[i].calOrd(); } sort(qr+1,qr+1+m,[](const query &A, const query &B) { return A.order<B.order; }); fill(ans,ans+1+n,0); int l=qr[1].l,r=qr[1].r; For(i,qr[1].l,qr[1].r) { if (i<0) break; trie1.add(s1[i]); } if (qr[1].l>0 && qr[1].r>0) ans[qr[1].ind]=trie1.getnum(qr[1].q); For(i,2,m) { if (qr[i].l<0 || qr[i].r<0) break; if (r<qr[i].r) For(j,r+1,qr[i].r) trie1.add(s1[j]); if (l>qr[i].l) For(j,qr[i].l,l-1) trie1.add(s1[j]); if (r>qr[i].l) For(j,qr[i].r+1,r) trie1.del(s1[j]); if (l<qr[i].l) For(j,l,qr[i].l-1) trie1.del(s1[j]); l=qr[i].l,r=qr[i].r; ans[qr[i].ind]=trie1.getnum(qr[i].q); } For(i,1,m) cout << ans[i] << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In member function 'void Trie::add(std::string, int)':
selling_rna.cpp:54:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |             int c = id[f];
      |                        ^
selling_rna.cpp: In member function 'bool Trie::delHandle(int, std::string&, int)':
selling_rna.cpp:70:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   70 |             int c = id[s[i]];
      |                            ^
selling_rna.cpp: In member function 'bool Trie::find(std::string&)':
selling_rna.cpp:89:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |             int c = id[f];
      |                        ^
selling_rna.cpp: In member function 'std::pair<int, int> Trie::get(std::string&)':
selling_rna.cpp:98:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   98 |             int c=id[f];
      |                      ^
selling_rna.cpp: In member function 'int Trie::getnum(std::string&)':
selling_rna.cpp:107:22: warning: array subscript has type 'char' [-Wchar-subscripts]
  107 |             int c=id[f];
      |                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...