oj.uz

Submission #923777

# Submission time Handle Problem Language Result Execution time Memory
923777 2024-02-07T18:24:58 Z CyberCow Grudanje (COCI19_grudanje) C++17
70 / 70
 862 ms 5908 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 3 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2396 KB Output is correct
2 Correct 17 ms 2396 KB Output is correct
3 Correct 16 ms 2636 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2392 KB Output is correct
2 Correct 18 ms 2392 KB Output is correct
3 Correct 17 ms 2636 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2396 KB Output is correct
2 Correct 17 ms 2396 KB Output is correct
3 Correct 16 ms 2396 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 856 ms 5644 KB Output is correct
2 Correct 836 ms 5640 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 5820 KB Output is correct
2 Correct 785 ms 5556 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 5908 KB Output is correct
2 Correct 804 ms 5784 KB Output is correct
3 Correct 796 ms 5640 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 5904 KB Output is correct
2 Correct 810 ms 5752 KB Output is correct
3 Correct 826 ms 5644 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 5648 KB Output is correct
2 Correct 834 ms 5904 KB Output is correct
3 Correct 779 ms 5648 KB Output is correct