제출 #38146

#제출 시각아이디문제언어결과실행 시간메모리
38146funcsrSelling RNA Strands (JOI16_selling_rna)C++14
100 / 100
973 ms154020 KiB
#include <iostream> #include <string> #include <vector> #include <queue> #include <set> #include <cassert> #include <algorithm> #define rep(i,n) for (int i=0; i<(n); i++) #define all(x) x.begin(), x.end() #define pb push_back #define _1 first #define _2 second using namespace std; typedef pair<int, int> P; string convert(string s) { string o = ""; for (char c : s) { if (c == 'A') o += 'a'; else if (c == 'G') o += 'b'; else if (c == 'C') o += 'c'; else o += 'd'; } return o; } string read() { string s; cin >> s; return convert(s); } struct BIT { vector<int> xs; int n; BIT(int n) : n(n) { xs.resize(n+1); } void add(int i, int v) { for (int x=i+1; x<=n; x+=x&-x) xs[x] += v; } int sum(int i) { int s = 0; for (int x=i+1; x>0; x-=x&-x) s += xs[x]; return s; } int sum(int l, int r) { return sum(r) - sum(l-1); } }; struct UF { vector<int> U, R; UF(int N) : U(N), R(N, 1) { rep(i, N) U[i] = i; } int find(int x) { if (U[x] == x) return x; return U[x] = find(U[x]); } void unite(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (R[x] < R[y]) swap(x, y); U[y] = x; R[x] += R[y]; } }; // with uniq vector<int> radixSort(int p, vector<int> all, vector<string> &src, UF &uf) { vector<int> s[5] = {}; vector<int> ret; for (int x : all) { if (src[x].size() == p) ret.pb(x); else s[src[x][p]-'a'].pb(x); } while (ret.size() > 1) { uf.unite(ret.front(), ret.back()); ret.pop_back(); } if (!ret.empty()) ret[0] = uf.find(ret[0]); rep(k, 5) if (!s[k].empty()) { vector<int> r = radixSort(p+1, s[k], src, uf); ret.insert(ret.end(), all(r)); } return ret; } int N, Q; string S[100000]; string Qpre[100000], Qsuf[100000]; int posX[300000], posY[300000]; int ans[100000]; vector<int> ps[300000]; int XL[100000], XR[100000]; vector<int> Qbegin[300000], Qend[300000]; int main() { cin >> N >> Q; rep(i, N) S[i] = read(); rep(i, Q) Qpre[i] = read(), Qsuf[i] = read(), reverse(all(Qsuf[i])); vector<string> xs, ys; rep(i, N) { // 0 ~ N-1 xs.pb(S[i]); string Srev(S[i]); reverse(all(Srev)); ys.pb(Srev); } rep(i, Q) { // N+q*2 <-> N+q*2+1 xs.pb(Qpre[i]); xs.pb(Qpre[i]+'e'); ys.pb(Qsuf[i]); ys.pb(Qsuf[i]+'e'); } vector<int> xsi, ysi; UF uf_x(N+2*Q), uf_y(N+2*Q); rep(i, N+2*Q) xsi.pb(i), ysi.pb(i); xsi = radixSort(0, xsi, xs, uf_x); ysi = radixSort(0, ysi, ys, uf_y); rep(i, N+2*Q) posX[i] = posY[i] = -1; rep(i, xsi.size()) posX[xsi[i]] = i; rep(i, ysi.size()) posY[ysi[i]] = i; rep(i, N+2*Q) { if (posX[i] == -1) posX[i] = posX[uf_x.find(i)]; if (posY[i] == -1) posY[i] = posY[uf_y.find(i)]; } BIT bit(xsi.size()); rep(i, N) ps[posY[i]].pb(posX[i]); rep(i, Q) { int xl = posX[N+i*2], xr = posX[N+i*2+1]; int yl = posY[N+i*2], yr = posY[N+i*2+1]; XL[i] = xl, XR[i] = xr; Qbegin[yl].pb(i); Qend[yr].pb(i); } rep(y, ysi.size()) { for (int q : Qbegin[y]) ans[q] -= bit.sum(XL[q], XR[q]); for (int x : ps[y]) bit.add(x, 1); for (int q : Qend[y]) ans[q] += bit.sum(XL[q], XR[q]); } rep(i, Q) cout << ans[i] << "\n"; return 0; }

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

selling_rna.cpp: In function 'std::vector<int> radixSort(int, std::vector<int>, std::vector<std::__cxx11::basic_string<char> >&, UF&)':
selling_rna.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (src[x].size() == p) ret.pb(x);
                       ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for (int i=0; i<(n); i++)
                                 ^
selling_rna.cpp:123:3: note: in expansion of macro 'rep'
   rep(i, xsi.size()) posX[xsi[i]] = i;
   ^
selling_rna.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for (int i=0; i<(n); i++)
                                 ^
selling_rna.cpp:124:3: note: in expansion of macro 'rep'
   rep(i, ysi.size()) posY[ysi[i]] = i;
   ^
selling_rna.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for (int i=0; i<(n); i++)
                                 ^
selling_rna.cpp:138:3: note: in expansion of macro 'rep'
   rep(y, ysi.size()) {
   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...