Submission #1212787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212787		vincentbucourt1	Grudanje (COCI19_grudanje)	C++20	70 / 70	474 ms	114760 KiB

grudanje

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
#define f first
#define s second

const int INF = (int)1e18;

int N, Q;
vector<int> word;
vector<int> whenCovered;
vector<pair<int,int>> queries;
int ans = 0;

struct Segtree {
    int numleaves;
    vector<pair<int,int>> tree;
    Segtree (int n) {
        numleaves = 1;
        while (numleaves < n) numleaves *= 2;
        tree.assign(2*numleaves, {-INF, -INF});
    }
    pair<int,int> combine (pair<int,int> a, pair<int,int> b) {
        if (a < b) {
            swap(a, b);
        }
        if (b.f > a.s) {
            a.s = b.f;
        }
        else if (b.s > a.s) {
            a.s = b.s;
        }
        return a;
    }
    pair<int,int> query (int l, int r) {
        pair<int,int> res = {-INF, -INF};
        l += numleaves, r += numleaves+1;
        while (l < r) {
            if (l&1) {
                res = combine(res, tree[l++]);
            }
            if (r&1) {
                res = combine(res, tree[--r]);
            }
            l /= 2, r /= 2;
        }
        return res;
    }
    void update (int idx, int val) {
        idx += numleaves;
        tree[idx] = {val, -INF};
        idx /= 2;
        while (idx > 0) {
            tree[idx] = combine(tree[2*idx], tree[2*idx+1]);
            idx /= 2;
        }
    }
};

signed main() {
    fastIO();
    string line;
    getline(cin, line);
    word.resize((int)line.size());
    for (int i = 0; i < (int)line.size(); i++) {
        word[i] = line[i] - 'a';
    }
    N = (int)word.size();
    cin >> Q;
    queries.resize(Q);
    for (int iq = 0; iq < Q; iq++) {
        cin >> queries[iq].f >> queries[iq].s;
        queries[iq].f--, queries[iq].s--;
    }
    whenCovered.resize(N);
    for (int i = 0; i < N; i++) {
        int p;
        cin >> p;
        p--;
        whenCovered[p] = i+1;
    }

    vector<Segtree> segQ(26, Segtree(N));
    for (int i = 0; i < N; i++) {
        segQ[word[i]].update(i, whenCovered[i]);
    }
    for (int iq = 0; iq < Q; iq++) {
        for (int letter = 0; letter < 26; letter++) {
            // assert((int)segQ[letter].tree.size() == 2*Segtree(N).numleaves);
            ans = max(ans, segQ[letter].query(queries[iq].f, queries[iq].s).s);
        }
    }
    cout << ans << "\n";
}

• 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