제출 #211390

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

selling_rna

#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];
    }
  );
  sort(str + 1, str + 1 + N);
  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: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40