oj.uz

Submission #38146

# Submission time Handle Problem Language Result Execution time Memory
38146 2018-01-02T07:08:45 Z funcsr Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 973 ms 154020 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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