# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
519261 |
2022-01-26T06:26:10 Z |
KoD |
Grudanje (COCI19_grudanje) |
C++17 |
|
149 ms |
24612 KB |
#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string S;
std::cin >> S;
const int N = S.size();
int Q;
std::cin >> Q;
vector<int> L(Q), R(Q);
for (int i = 0; i < Q; ++i) {
std::cin >> L[i] >> R[i];
L[i] -= 1;
}
vector<int> P(N);
for (auto& x : P) {
std::cin >> x;
x -= 1;
}
int ok = N, ng = -1;
array<vector<int>, 26> sum;
sum.fill(vector<int>(N + 1));
while (ok - ng > 1) {
const int md = (ok + ng) / 2;
array<vector<int>, 26> sum;
sum.fill(vector<int>(N + 1));
for (int i = md; i < N; ++i) {
sum[S[P[i]] - 'a'][P[i] + 1] += 1;
}
bool f = true;
for (int k = 0; k < 26; ++k) {
for (int i = 0; i < N; ++i) {
sum[k][i + 1] += sum[k][i];
}
for (int j = 0; j < Q; ++j) {
if (sum[k][R[j]] - sum[k][L[j]] > 1) {
f = false;
break;
}
}
if (!f) {
break;
}
}
(f ? ok : ng) = md;
}
std::cout << ok << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1012 KB |
Output is correct |
2 |
Correct |
3 ms |
1020 KB |
Output is correct |
3 |
Correct |
3 ms |
1052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1004 KB |
Output is correct |
2 |
Correct |
3 ms |
1020 KB |
Output is correct |
3 |
Correct |
2 ms |
1004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1012 KB |
Output is correct |
2 |
Correct |
3 ms |
1016 KB |
Output is correct |
3 |
Correct |
3 ms |
1064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
130 ms |
24436 KB |
Output is correct |
2 |
Correct |
105 ms |
24612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
24408 KB |
Output is correct |
2 |
Correct |
94 ms |
24332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
140 ms |
24400 KB |
Output is correct |
2 |
Correct |
133 ms |
24392 KB |
Output is correct |
3 |
Correct |
101 ms |
24336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
149 ms |
24392 KB |
Output is correct |
2 |
Correct |
142 ms |
24520 KB |
Output is correct |
3 |
Correct |
106 ms |
24436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
147 ms |
24408 KB |
Output is correct |
2 |
Correct |
135 ms |
24460 KB |
Output is correct |
3 |
Correct |
123 ms |
24360 KB |
Output is correct |