oj.uz

Submission #211389

# Submission time Handle Problem Language Result Execution time Memory
211389 2020-03-20T08:47:55 Z quocnguyen1012 Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 69 ms 36740 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5, base = 131;
const ll llinf = 1e18;

string str[maxn], p[maxn], q[maxn];
int N, M;
int id[maxn], pos[maxn];
int BIT[maxn];
int res[maxn];
int nl[maxn], nr[maxn];
vector<int> add[maxn], rem[maxn];

void upd(int i, int v)
{
  for(; i < maxn; i += i & -i)
    BIT[i] += v;
}

int sum(int i)
{
  int res = 0;
  for(; i; i -= i & -i)
    res += BIT[i];
  return res;
}

int rsum(int l, int r)
{
  return sum(r) - sum(l - 1);
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> M;
  for(int i = 1; i <= N; ++i){
    cin >> str[i];
    id[i] = i;
  }
  for(int i = 1; i <= M; ++i){
    cin >> p[i] >> q[i];
  }
  sort(str + 1, str + 1 + N);
  for(int i = 1; i <= M; ++i){
    int l = lower_bound(str + 1, str + 1 + N, p[i]) - str;
    add[l].eb(i);
    ++p[i].back();
    int r = lower_bound(str + 1, str + 1 + N, p[i]) - str;
    rem[r].eb(i);
  }
  for(int i = 1; i <= N; ++i){
    reverse(str[i].begin(), str[i].end());
  }
  sort(id + 1, id + 1 + N,[&](int x, int y)
    {
      return str[x] < str[y];
    }
  );
  for(int i = 1; i <= M; ++i){
    reverse(q[i].begin(), q[i].end());
    nl[i] = lower_bound(str + 1, str + 1 + N, q[i]) - str;
    ++q[i].back();
    nr[i] = upper_bound(str + 1, str + 1 + N, q[i]) - str - 1;
  }
  for(int i = 1; i <= N; ++i)
    pos[id[i]] = i;
  for(int i = N; i >= 1; --i){
    upd(pos[i], 1);
    for(int id : add[i]) res[id] += rsum(nl[id], nr[id]);
    for(int id : rem[i]) res[id] -= rsum(nl[id], nr[id]);
  }
  for(int i = 1; i <= M; ++i)
    cout << res[i] << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 28544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 36740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 30968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 28544 KB Output isn't correct
2 Halted 0 ms 0 KB -