#include <bits/stdc++.h>
#define F first
#define S second
#define T int t; cin >> t; while(t--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e5 + 5;
const int M = 1e3 + 3;
const int inf = 1e18;
const int mod = 1e9 + 7;
int n, q, a[N];
pair<int, int> p[N], tree[30][4 * N];
string s;
pair<int, int> getMax(pair<int, int> p1, pair<int, int> p2) {
vector<int> v;
v.push_back(p1.F);
v.push_back(p1.S);
v.push_back(p2.F);
v.push_back(p2.S);
sort(begin(v), end(v));
return {v[3], v[2]};
}
void build(int letter, int node, int tl, int tr) {
if (tr == tl) {
if (s[tr] == (letter + 'a')) tree[letter][node] = {a[tl], 0};
return;
}
int mid = (tl + tr) / 2;
build(letter, 2 * node, tl, mid);
build(letter, 2 * node + 1, mid + 1, tr);
tree[letter][node] = getMax(tree[letter][2 * node], tree[letter][2 * node + 1]);
}
pair<int, int> get(int letter, int node, int tl, int tr, int l, int r) {
if (tr < l || tl > r) return {0, 0};
if (l <= tl && tr <= r) return tree[letter][node];
int mid = (tl + tr) / 2;
pair<int, int> p1 = get(letter, 2 * node, tl, mid, l, r);
pair<int, int> p2 = get(letter, 2 * node + 1, mid + 1, tr, l, r);
return getMax(p1, p2);
}
main() {
IOS
cin >> s;
n = s.size();
s = '.' + s;
cin >> q;
for(int i = 1; i <= q; i++) cin >> p[i].F >> p[i].S;
sort(p, p + q + 1);
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
a[x] = i;
}
int mx = 0;
for(int j = 0; j < 26; j++)
build(j, 1, 1, n);
for(int i = 1; i <= q; i++) {
for(int j = 0; j < 26; j++) {
int l = p[i].F, r = p[i].S;
int need = get(j, 1, 1, n, l, r).S;
mx = max(mx, need);
}
}
cout << mx << '\n';
}
Compilation message
grudanje.cpp:10:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
10 | const int inf = 1e18;
| ^~~~
grudanje.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
46 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
724 KB |
Output is correct |
2 |
Correct |
17 ms |
664 KB |
Output is correct |
3 |
Correct |
20 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
724 KB |
Output is correct |
2 |
Correct |
18 ms |
660 KB |
Output is correct |
3 |
Correct |
18 ms |
652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
146 ms |
2132 KB |
Output is correct |
2 |
Correct |
143 ms |
1612 KB |
Output is correct |
3 |
Correct |
145 ms |
1452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
2132 KB |
Output is correct |
2 |
Correct |
138 ms |
1528 KB |
Output is correct |
3 |
Correct |
145 ms |
1452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
150 ms |
2208 KB |
Output is correct |
2 |
Correct |
144 ms |
1428 KB |
Output is correct |
3 |
Correct |
144 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2090 ms |
29532 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2076 ms |
29564 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2075 ms |
55084 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2085 ms |
55196 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2082 ms |
55112 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |