oj.uz

Submission #562756

# Submission time Handle Problem Language Result Execution time Memory
562756 2022-05-15T08:15:59 Z SSRS Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 13124 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;
  }
  for (int i = 0; i < M; i++){
    string P, Q;
    cin >> P >> Q;
    reverse(Q.begin(), Q.end());
    int L1 = lower_bound(P1.begin(), P1.end(), make_pair(P, 0)) - P1.begin();
    P.back()++;
    int R1 = lower_bound(P1.begin(), P1.end(), make_pair(P, 0)) - P1.begin();
    int L2 = lower_bound(P2.begin(), P2.end(), make_pair(Q, 0)) - P2.begin();
    Q.back()++;
    int R2 = lower_bound(P2.begin(), P2.end(), make_pair(Q, N)) - P2.begin();
    int ans = 0;
    for (int j = 0; j < N; j++){
      if (L1 <= X[j] && X[j] < R1 && L2 <= Y[j] && Y[j] < R2){
        ans++;
      }
    }
    cout << ans << 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 113 ms 7372 KB Output is correct
2 Correct 232 ms 7732 KB Output is correct
3 Correct 178 ms 7796 KB Output is correct
4 Correct 222 ms 7852 KB Output is correct
5 Correct 153 ms 5216 KB Output is correct
6 Correct 160 ms 5436 KB Output is correct
7 Correct 142 ms 5608 KB Output is correct
8 Correct 245 ms 7384 KB Output is correct
9 Correct 242 ms 13124 KB Output is correct
10 Correct 125 ms 10712 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1573 ms 6444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
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 113 ms 7372 KB Output is correct
9 Correct 232 ms 7732 KB Output is correct
10 Correct 178 ms 7796 KB Output is correct
11 Correct 222 ms 7852 KB Output is correct
12 Correct 153 ms 5216 KB Output is correct
13 Correct 160 ms 5436 KB Output is correct
14 Correct 142 ms 5608 KB Output is correct
15 Correct 245 ms 7384 KB Output is correct
16 Correct 242 ms 13124 KB Output is correct
17 Correct 125 ms 10712 KB Output is correct
18 Execution timed out 1573 ms 6444 KB Time limit exceeded
19 Halted 0 ms 0 KB -