답안 #38146 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38146	2018-01-02T07:08:45 Z	funcsr	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	973 ms	154020 KB

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;
}

Compilation message

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	36012 KB	Output is correct
2	Correct	9 ms	36012 KB	Output is correct
3	Correct	13 ms	36012 KB	Output is correct
4	Correct	13 ms	36012 KB	Output is correct
5	Correct	6 ms	36012 KB	Output is correct
6	Correct	6 ms	36012 KB	Output is correct
7	Correct	16 ms	36012 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	779 ms	112360 KB	Output is correct
2	Correct	796 ms	110712 KB	Output is correct
3	Correct	973 ms	111908 KB	Output is correct
4	Correct	919 ms	110764 KB	Output is correct
5	Correct	896 ms	48244 KB	Output is correct
6	Correct	833 ms	48272 KB	Output is correct
7	Correct	706 ms	114008 KB	Output is correct
8	Correct	959 ms	79532 KB	Output is correct
9	Correct	966 ms	85320 KB	Output is correct
10	Correct	563 ms	72824 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	83 ms	60508 KB	Output is correct
2	Correct	73 ms	50024 KB	Output is correct
3	Correct	86 ms	50520 KB	Output is correct
4	Correct	79 ms	49004 KB	Output is correct
5	Correct	59 ms	49528 KB	Output is correct
6	Correct	79 ms	50052 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	36012 KB	Output is correct
2	Correct	9 ms	36012 KB	Output is correct
3	Correct	13 ms	36012 KB	Output is correct
4	Correct	13 ms	36012 KB	Output is correct
5	Correct	6 ms	36012 KB	Output is correct
6	Correct	6 ms	36012 KB	Output is correct
7	Correct	16 ms	36012 KB	Output is correct
8	Correct	779 ms	112360 KB	Output is correct
9	Correct	796 ms	110712 KB	Output is correct
10	Correct	973 ms	111908 KB	Output is correct
11	Correct	919 ms	110764 KB	Output is correct
12	Correct	896 ms	48244 KB	Output is correct
13	Correct	833 ms	48272 KB	Output is correct
14	Correct	706 ms	114008 KB	Output is correct
15	Correct	959 ms	79532 KB	Output is correct
16	Correct	966 ms	85320 KB	Output is correct
17	Correct	563 ms	72824 KB	Output is correct
18	Correct	83 ms	60508 KB	Output is correct
19	Correct	73 ms	50024 KB	Output is correct
20	Correct	86 ms	50520 KB	Output is correct
21	Correct	79 ms	49004 KB	Output is correct
22	Correct	59 ms	49528 KB	Output is correct
23	Correct	79 ms	50052 KB	Output is correct
24	Correct	843 ms	116620 KB	Output is correct
25	Correct	923 ms	123000 KB	Output is correct
26	Correct	759 ms	112260 KB	Output is correct
27	Correct	779 ms	116392 KB	Output is correct
28	Correct	806 ms	154020 KB	Output is correct
29	Correct	599 ms	88404 KB	Output is correct

답안 #38146

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 25.0 / 25.0

Subtask #3 25.0 / 25.0

Subtask #4 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
25.0 / 25.0

Subtask #3
25.0 / 25.0

Subtask #4
40.0 / 40.0