oj.uz

Submission #982350

# Submission time Handle Problem Language Result Execution time Memory
982350 2024-05-14T07:13:21 Z davitmarg Sequence (APIO23_sequence) C++17
50 / 100
 2000 ms 66128 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#include <fstream>
#define fastIO                   \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 500005;

int n, a[N], ans = 1;
vector<int> pos[N];
pair<int, int> t[N * 4];
pair<int, int> t2[N * 4];
int d[N * 4];
int d2[N * 4];

pair<int, int> merge(pair<int, int> a, pair<int, int> b)
{
    return MP(min(a.first, b.first), max(a.second, b.second));
}

void build(int v, int l, int r)
{
    t[v] = t2[v] = MP(l, l);
    d[v] = d2[v] = 0;
    if (l == r)
        return;
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    t[v] = merge(t[v * 2], t[v * 2 + 1]);
    t2[v] = merge(t2[v * 2], t2[v * 2 + 1]);
}

void push(int v, int l, int r)
{
    if (d[v] == 0)
        return;
    if (l != r)
    {
        d[v * 2] += d[v];
        d[v * 2 + 1] += d[v];
    }
    t[v] = MP(t[v].first + d[v], t[v].second + d[v]);
    d[v] = 0;
}

void add(int v, int l, int r, int i, int j, int val)
{
    push(v, l, r);
    if (i > j)
        return;
    if (i == l && j == r)
    {
        d[v] += val;
        push(v, l, r);
        return;
    }

    int m = (l + r) / 2;
    add(v * 2, l, m, i, min(m, j), val);
    add(v * 2 + 1, m + 1, r, max(m + 1, i), j, val);
    t[v] = merge(t[v * 2], t[v * 2 + 1]);
}

pair<int, int> get(int v, int l, int r, int i, int j)
{
    push(v, l, r);
    if (i > j)
        return MP(mod, -mod);
    if (i == l && j == r)
        return t[v];

    int m = (l + r) / 2;
    return merge(
        get(v * 2, l, m, i, min(m, j)),
        get(v * 2 + 1, m + 1, r, max(m + 1, i), j)
    );
}

void push2(int v, int l, int r)
{
    if (d2[v] == 0)
        return;
    if (l != r)
    {
        d2[v * 2] += d2[v];
        d2[v * 2 + 1] += d2[v];
    }
    t2[v] = MP(t2[v].first + d2[v], t2[v].second + d2[v]);
    d2[v] = 0;
}

void add2(int v, int l, int r, int i, int j, int val)
{
    push2(v, l, r);
    if (i > j)
        return;
    if (i == l && j == r)
    {
        d2[v] += val;
        push2(v, l, r);
        return;
    }

    int m = (l + r) / 2;
    add2(v * 2, l, m, i, min(m, j), val);
    add2(v * 2 + 1, m + 1, r, max(m + 1, i), j, val);
    t2[v] = merge(t2[v * 2], t2[v * 2 + 1]);
}

pair<int, int> get2(int v, int l, int r, int i, int j)
{
    push2(v, l, r);
    if (i > j)
        return MP(mod, -mod);
    if (i == l && j == r)
        return t2[v];

    int m = (l + r) / 2;
    return merge(
        get2(v * 2, l, m, i, min(m, j)),
        get2(v * 2 + 1, m + 1, r, max(m + 1, i), j)
    );
}


bool check(int x, int k, int p)
{
    int i = pos[x][p];

    int j = pos[x][k];
    int len = p - k + 1;

    pair<int, int> dr = get(1, 0, n, i, n);
    dr.first -= len;
    dr.second -= len;
    pair<int, int> dl = get(1, 0, n, 0, j - 1);
    pair<int, int> d = MP(dr.first - dl.second, dr.second - dl.first);


    pair<int, int> dr2 = get2(1, 0, n, i, n);
    dr2.first += len;
    dr2.second += len;
    pair<int, int> dl2 = get2(1, 0, n, 0, j - 1);
    pair<int, int> d2 = MP(dr2.first - dl2.second, dr2.second - dl2.first);

    return ((d.second < 0 && len >= -d.second) || (d.first > 0 && len >= d.first) || (d.first <= 0 && d.second >= 0) || (d2.second < 0 && len >= -d2.second) || (d2.first > 0 && len >= d2.first) || (d2.first <= 0 && d2.second >= 0));
}

bool check(int x, int len)
{
    for (int p = -1 + pos[x].size(); p >= len - 1; p--)
    {
        if (check(x, p - len + 1, p))
            return true;
    }
    return false;
}

int sequence(int nn, vector<int> aa)
{
    n = nn;
    for (int i = 1; i <= n; i++)
        a[i] = aa[i - 1];

    for (int i = 1; i <= n; i++)
        pos[a[i]].push_back(i);


    int l = 1;
    int r = n;

    while (l <= r)
    {
        build(1, 0, n);

        int m = (l + r) / 2;

        bool f = false;

        for (int x = 1; x <= n; x++)
        {
            for (int p = 0; p < pos[x].size(); p++)
            {
                int i = pos[x][p];
                add2(1, 0, n, i, n, -2);
            }

            if (check(x, m))
            {
                f = true;
                break;
            }

            for (int p = 0; p < pos[x].size(); p++)
            {
                int i = pos[x][p];
                add(1, 0, n, i, n, -2);
            }

        }

        if(f)
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }


    return ans;
}

#ifdef death



void solve()
{
    int nn;
    vector<int> aa;
    cin >> nn;
    for (int i = 0; i < nn; i++)
    {
        int x;
        cin >> x;
        aa.push_back(x);
    }

    cout << sequence(nn, aa) << endl;
}

int main()
{
    fastIO;
    int T = 1;
    //cin >> T;
    while (T--)
        solve();
    return 0;
}
#endif // death

/*

7
1 2 3 1 2 1 3

9
1 1 2 3 4 3 2 1 1

14
2 6 2 5 3 4 2 1 4 3 5 6 3 2

*/

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:208:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |             for (int p = 0; p < pos[x].size(); p++)
      |                             ~~^~~~~~~~~~~~~~~
sequence.cpp:220:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  220 |             for (int p = 0; p < pos[x].size(); p++)
      |                             ~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20968 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20828 KB Output is correct
8 Correct 4 ms 20824 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20972 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20968 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20828 KB Output is correct
8 Correct 4 ms 20824 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20972 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 12 ms 20828 KB Output is correct
14 Correct 12 ms 21032 KB Output is correct
15 Correct 10 ms 21012 KB Output is correct
16 Correct 10 ms 20828 KB Output is correct
17 Correct 11 ms 20828 KB Output is correct
18 Correct 10 ms 21052 KB Output is correct
19 Correct 11 ms 20828 KB Output is correct
20 Correct 11 ms 21080 KB Output is correct
21 Correct 14 ms 21028 KB Output is correct
22 Correct 12 ms 20828 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Execution timed out 2059 ms 60540 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Execution timed out 2036 ms 52736 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2012 ms 66128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20968 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20828 KB Output is correct
8 Correct 4 ms 20824 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20972 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 12 ms 20828 KB Output is correct
14 Correct 12 ms 21032 KB Output is correct
15 Correct 10 ms 21012 KB Output is correct
16 Correct 10 ms 20828 KB Output is correct
17 Correct 11 ms 20828 KB Output is correct
18 Correct 10 ms 21052 KB Output is correct
19 Correct 11 ms 20828 KB Output is correct
20 Correct 11 ms 21080 KB Output is correct
21 Correct 14 ms 21028 KB Output is correct
22 Correct 12 ms 20828 KB Output is correct
23 Correct 751 ms 31548 KB Output is correct
24 Correct 732 ms 31548 KB Output is correct
25 Correct 742 ms 31552 KB Output is correct
26 Correct 542 ms 30804 KB Output is correct
27 Correct 609 ms 30556 KB Output is correct
28 Correct 607 ms 30620 KB Output is correct
29 Correct 466 ms 30364 KB Output is correct
30 Correct 447 ms 30428 KB Output is correct
31 Correct 307 ms 30420 KB Output is correct
32 Correct 494 ms 32344 KB Output is correct
33 Correct 533 ms 31572 KB Output is correct
34 Correct 656 ms 31372 KB Output is correct
35 Correct 599 ms 31320 KB Output is correct
36 Correct 663 ms 31320 KB Output is correct
37 Correct 733 ms 31328 KB Output is correct
38 Correct 770 ms 31372 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20968 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 4 ms 20828 KB Output is correct
8 Correct 4 ms 20824 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 4 ms 20972 KB Output is correct
12 Correct 4 ms 20828 KB Output is correct
13 Correct 12 ms 20828 KB Output is correct
14 Correct 12 ms 21032 KB Output is correct
15 Correct 10 ms 21012 KB Output is correct
16 Correct 10 ms 20828 KB Output is correct
17 Correct 11 ms 20828 KB Output is correct
18 Correct 10 ms 21052 KB Output is correct
19 Correct 11 ms 20828 KB Output is correct
20 Correct 11 ms 21080 KB Output is correct
21 Correct 14 ms 21028 KB Output is correct
22 Correct 12 ms 20828 KB Output is correct
23 Execution timed out 2059 ms 60540 KB Time limit exceeded
24 Halted 0 ms 0 KB -