Submission #923777

#	Time	Username	Problem	Language	Result	Execution time	Memory
923777		CyberCow	Grudanje (COCI19_grudanje)	C++17	70 / 70	862 ms	5908 KiB

grudanje

#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((x).size())
typedef long long ll;
using namespace std;
mt19937 rnd(348502);
const ll N = 100010;
ll mod = 1e9 + 7;

pair<int, int> s[4 * N];
string ss;
int a[N];

void build(int p, int lp, int rp, char ch)
{
    if (lp == rp)
    {
        if (ss[lp] == ch)
            s[p].first = a[lp];
        else
            s[p].first = 0;
        return;
    }
    int m = (lp + rp) / 2;
    build(p * 2, lp, m, ch);
    build(p * 2 + 1, m + 1, rp, ch);
    s[p].first = max(s[p * 2].first, s[p * 2 + 1].first);
    if (s[p].first == s[p * 2].first)
    {
        s[p].second = max(s[p * 2].second, s[p * 2 + 1].first);
    }
    else
    {
        s[p].second = max(s[p * 2].first, s[p * 2 + 1].second);
    }
}

pair<int, int> get_ma(int p, int lp, int rp, int l, int r)
{
    if (l > r)
        return { 0, 0 };
    if (lp == l && rp == r)
    {
        return s[p];
    }
    int m = (lp + rp) / 2;
    pair<int, int> gg = get_ma(p * 2, lp, m, l, min(m, r));
    pair<int, int> gg1 = get_ma(p * 2 + 1, m + 1, rp, max(l, m + 1), r);
    if (gg.first < gg1.first)
        return { gg1.first, max(gg.first, gg1.second) };
    return { gg.first, max(gg1.first, gg.second) };
}

void solve()
{
    int n, i, j, x, y, q;
    cin >> ss >> q;
    vector<pair<int, int>> quer;
    for ( i = 0; i < q; i++)
    {
        cin >> x >> y;
        quer.push_back({ x, y });
    }
    vector<int> v;
    for ( i = 0; i < ss.size(); i++)
    {
        cin >> x;
        a[x - 1] = i + 1;
    }
    int ans = 0;
    for (char c = 'a'; c <= 'z'; c++)
    {
        build(1, 0, ss.size() - 1, c);
        for ( i = 0; i < quer.size(); i++)
        {
            ans = max(ans, get_ma(1, 0, ss.size() - 1, quer[i].first - 1, quer[i].second - 1).second);
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

grudanje.cpp: In function 'void solve()':
grudanje.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for ( i = 0; i < ss.size(); i++)
      |                  ~~^~~~~~~~~~~
grudanje.cpp:93:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for ( i = 0; i < quer.size(); i++)
      |                      ~~^~~~~~~~~~~~~
grudanje.cpp:75:9: warning: unused variable 'n' [-Wunused-variable]
   75 |     int n, i, j, x, y, q;
      |         ^
grudanje.cpp:75:15: warning: unused variable 'j' [-Wunused-variable]
   75 |     int n, i, j, x, y, q;
      |               ^

• 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