oj.uz

Submission #891704

# Submission time Handle Problem Language Result Execution time Memory
891704 2023-12-23T17:08:03 Z ind1v Grudanje (COCI19_grudanje) C++11
70 / 70
 136 ms 26196 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define db(x) cout << "[" << #x << "]: " << x << '\n';

const int N = 1e5 + 4;

int a[N], b[N], d[N], p[N];
int pr[N][26];
int n, q;
bool m[N];
char x;

bool check(int md) {
  memset(m, 0, sizeof(m));
  for (int i = 1; i <= md; ++i) {
    m[p[i]] = 1;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 26; ++j) {
      pr[i][j] = pr[i - 1][j];
    }
    if (!m[i]) {
      ++pr[i][d[i]];
    }
  }
  bool f = true;
  for (int i = 1; i <= q; ++i) {
    for (int j = 0; j < 26; ++j) {
      f &= (pr[b[i]][j] - pr[a[i] - 1][j] <= 1);
    }
  }
  return f;
}

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s; cin >> s;
  n = sz(s);
  for (int i = 1; i <= n; ++i) {
    d[i] = (int)(s[i - 1] - 'a');
  }
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    cin >> a[i] >> b[i];
  }
  for (int i = 1; i <= n; ++i) {
    cin >> p[i];
  }
  int l = 0, r = n;
  while (l < r) {
    int md = (l + r) / 2;
    if (check(md)) r = md;
    else l = md + 1;
  }
  cout << l;
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6772 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6936 KB Output is correct
2 Correct 3 ms 6672 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 26088 KB Output is correct
2 Correct 120 ms 25984 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 26092 KB Output is correct
2 Correct 115 ms 25980 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 25948 KB Output is correct
2 Correct 121 ms 26088 KB Output is correct
3 Correct 114 ms 26000 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 25944 KB Output is correct
2 Correct 129 ms 26084 KB Output is correct
3 Correct 115 ms 25988 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 26196 KB Output is correct
2 Correct 119 ms 26088 KB Output is correct
3 Correct 114 ms 25936 KB Output is correct