oj.uz

Submission #685214

# Submission time Handle Problem Language Result Execution time Memory
685214 2023-01-23T17:10:19 Z Farhan_HY Grudanje (COCI19_grudanje) C++14
70 / 70
 1188 ms 55212 KB 
#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) {
    int mx = 0, mx2 = 0;
    mx = max({p1.F, p1.S, p2.F, p2.S});
    if (p1.F == mx) p1.F = 0;
    else if (p1.S == mx) p1.S = 0;
    else if (p2.F == mx) p2.F = 0;
    else if (p2.S == mx) p2.S = 0;
    mx2 = max({p1.F, p1.S, p2.F, p2.S});
    return {mx, mx2};
}

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:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main() {
      | ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 4 ms 652 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 5 ms 596 KB Output is correct
3 Correct 4 ms 596 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2132 KB Output is correct
2 Correct 18 ms 1536 KB Output is correct
3 Correct 22 ms 1364 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2204 KB Output is correct
2 Correct 20 ms 1532 KB Output is correct
3 Correct 26 ms 1364 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2132 KB Output is correct
2 Correct 17 ms 1492 KB Output is correct
3 Correct 25 ms 1476 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 29608 KB Output is correct
2 Correct 912 ms 31356 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 993 ms 29604 KB Output is correct
2 Correct 915 ms 31384 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1188 ms 55208 KB Output is correct
2 Correct 958 ms 34536 KB Output is correct
3 Correct 869 ms 32380 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1110 ms 55212 KB Output is correct
2 Correct 1008 ms 34536 KB Output is correct
3 Correct 844 ms 32376 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1074 ms 55196 KB Output is correct
2 Correct 954 ms 34536 KB Output is correct
3 Correct 885 ms 32384 KB Output is correct