oj.uz

Submission #562759

# Submission time Handle Problem Language Result Execution time Memory
562759 2022-05-15T08:25:08 Z SSRS Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 502 ms 38508 KB 
#include <bits/stdc++.h>
using namespace std;
struct binary_indexed_tree{
  int N;
  vector<int> BIT;
  binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
  }
  void add(int i){
    i++;
    while (i <= N){
      BIT[i]++;
      i += i & -i;
    }
  }
  int sum(int i){
    int ans = 0;
    while (i > 0){
      ans += BIT[i];
      i -= i & -i;
    }
    return ans;
  }
  int sum(int L, int R){
    return sum(R) - sum(L);
  }
};
int main(){
  int N, M;
  cin >> N >> M;
  vector<string> S(N);
  for (int i = 0; i < N; i++){
    cin >> S[i];
  }
  vector<pair<string, int>> P1(N);
  for (int i = 0; i < N; i++){
    P1[i] = make_pair(S[i], i);
  }
  for (int i = 0; i < N; i++){
    reverse(S[i].begin(), S[i].end());
  }
  vector<pair<string, int>> P2(N);
  for (int i = 0; i < N; i++){
    P2[i] = make_pair(S[i], i);
  }
  sort(P1.begin(), P1.end());
  sort(P2.begin(), P2.end());
  vector<int> X(N), Y(N);
  for (int i = 0; i < N; i++){
    X[P1[i].second] = i;
    Y[P2[i].second] = i;
  }
  vector<int> L1(M), R1(M), L2(M), R2(M);
  for (int i = 0; i < M; i++){
    string P, Q;
    cin >> P >> Q;
    reverse(Q.begin(), Q.end());
    L1[i] = lower_bound(P1.begin(), P1.end(), make_pair(P, 0)) - P1.begin();
    P.back()++;
    R1[i] = lower_bound(P1.begin(), P1.end(), make_pair(P, 0)) - P1.begin();
    L2[i] = lower_bound(P2.begin(), P2.end(), make_pair(Q, 0)) - P2.begin();
    Q.back()++;
    R2[i] = lower_bound(P2.begin(), P2.end(), make_pair(Q, N)) - P2.begin();
  }
  vector<vector<int>> query_add(N + 1), query_sub(N + 1);
  for (int i = 0; i < M; i++){
    query_sub[L1[i]].push_back(i);
    query_add[R1[i]].push_back(i);
  }
  vector<vector<int>> update(N + 1);
  for (int i = 0; i < N; i++){
    update[X[i]].push_back(Y[i]);
  }
  vector<int> ans(M, 0);
  binary_indexed_tree BIT(N);
  for (int i = 0; i <= N; i++){
    for (int j : query_add[i]){
      ans[j] += BIT.sum(L2[j], R2[j]);
    }
    for (int j : query_sub[i]){
      ans[j] -= BIT.sum(L2[j], R2[j]);
    }
    for (int j : update[i]){
      BIT.add(j);
    }
  }
  for (int i = 0; i < M; i++){
    cout << ans[i] << endl;
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 7656 KB Output is correct
2 Correct 121 ms 8536 KB Output is correct
3 Correct 113 ms 8064 KB Output is correct
4 Correct 108 ms 8472 KB Output is correct
5 Correct 75 ms 5980 KB Output is correct
6 Correct 80 ms 6028 KB Output is correct
7 Correct 141 ms 5908 KB Output is correct
8 Correct 161 ms 8100 KB Output is correct
9 Correct 153 ms 8092 KB Output is correct
10 Correct 99 ms 8016 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 13212 KB Output is correct
2 Correct 102 ms 8296 KB Output is correct
3 Correct 129 ms 10928 KB Output is correct
4 Correct 125 ms 9264 KB Output is correct
5 Correct 135 ms 8440 KB Output is correct
6 Correct 129 ms 10996 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 93 ms 7656 KB Output is correct
9 Correct 121 ms 8536 KB Output is correct
10 Correct 113 ms 8064 KB Output is correct
11 Correct 108 ms 8472 KB Output is correct
12 Correct 75 ms 5980 KB Output is correct
13 Correct 80 ms 6028 KB Output is correct
14 Correct 141 ms 5908 KB Output is correct
15 Correct 161 ms 8100 KB Output is correct
16 Correct 153 ms 8092 KB Output is correct
17 Correct 99 ms 8016 KB Output is correct
18 Correct 191 ms 13212 KB Output is correct
19 Correct 102 ms 8296 KB Output is correct
20 Correct 129 ms 10928 KB Output is correct
21 Correct 125 ms 9264 KB Output is correct
22 Correct 135 ms 8440 KB Output is correct
23 Correct 129 ms 10996 KB Output is correct
24 Correct 187 ms 14256 KB Output is correct
25 Correct 240 ms 15472 KB Output is correct
26 Correct 132 ms 13900 KB Output is correct
27 Correct 194 ms 14420 KB Output is correct
28 Correct 502 ms 38508 KB Output is correct
29 Correct 482 ms 29232 KB Output is correct