제출 #891704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
891704		ind1v	Grudanje (COCI19_grudanje)	C++11	70 / 70	136 ms	26196 KiB

grudanje

#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 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7