제출 #38146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38146		funcsr	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	973 ms	154020 KiB

selling_rna

#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()) {
   ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40