Submission #258416

#	Time	Username	Problem	Language	Result	Execution time	Memory
258416		ipaljak	Grudanje (COCI19_grudanje)	C++14	70 / 70	234 ms	14100 KiB

grudanje

#include <bits/stdc++.h>

using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<

typedef long long llint;

const int MAXN = 1e5 + 10;

char s[MAXN];

int n, q;
int l[MAXN], r[MAXN], p[MAXN], pp[MAXN], pref[26][MAXN];

bool check(int x) {
  for (int i = 0; i < 26; ++i) pref[i][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 26; ++j)
      pref[j][i + 1] = pref[j][i];
    if (pp[i] > x)
      pref[s[i] - 'a'][i + 1] += 1;
  }
  bool ok = true;
  for (int i = 0; i < q && ok; ++i)
    for (int j = 0; j < 26 && ok; ++j)
      ok &= (pref[j][r[i]] - pref[j][l[i] - 1]) <= 1;
  return ok;
}

int main(void) {
  scanf("%s", s);
  n = strlen(s);

  scanf("%d", &q);
  for (int i = 0; i < q; ++i)
    scanf("%d%d", &l[i], &r[i]);

  for (int i = 0; i < n; ++i) {
    scanf("%d", &p[i]); --p[i];
    pp[p[i]] = i + 1;
  }

  int lo = 0, hi = n;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (check(mid)) hi = mid; else lo = mid + 1;
  }

  printf("%d\n", lo);
  return 0;
}

Compilation message (stderr)

grudanje.cpp: In function 'int main()':
grudanje.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~
grudanje.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
grudanje.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &l[i], &r[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
grudanje.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p[i]); --p[i];
     ~~~~~^~~~~~~~~~~~~

• 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