oj.uz

Submission #982312

# Submission time Handle Problem Language Result Execution time Memory
982312 2024-05-14T06:31:22 Z davitmarg Sequence (APIO23_sequence) C++17
13 / 100
 2000 ms 64880 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 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 = len - 1; p < pos[x].size(); p++)
    {
        if (rand() % 10 == 0)
            continue;
        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);

    for (int i = 1; i <= n; i++)
    {
        add(1, 0, n, i, n, 1);
        add2(1, 0, n, i, n, 1);
    }

    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);
        }

        int l = ans, r = pos[x].size();

        while (l <= r)
        {
            int m = (l + r) / 2;
            if (check(x, m))
            {
                ans = max(ans, m);
                l = m + 1;
            }
            else
                r = m - 1;
        }

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


    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 'bool check(int, int)':
sequence.cpp:164:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for (int p = len - 1; p < pos[x].size(); p++)
      |                           ~~^~~~~~~~~~~~~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:191:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         for (int p = 0; p < pos[x].size(); p++)
      |                         ~~^~~~~~~~~~~~~~~
sequence.cpp:211:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |         for (int p = 0; p < pos[x].size(); p++)
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18920 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 4 ms 18776 KB Output is correct
7 Correct 3 ms 19032 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 4 ms 18868 KB Output is correct
10 Correct 4 ms 18780 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Incorrect 3 ms 18780 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18920 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 4 ms 18776 KB Output is correct
7 Correct 3 ms 19032 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 4 ms 18868 KB Output is correct
10 Correct 4 ms 18780 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Incorrect 3 ms 18780 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 516 ms 59008 KB Output is correct
3 Correct 533 ms 59072 KB Output is correct
4 Correct 854 ms 51160 KB Output is correct
5 Correct 525 ms 58136 KB Output is correct
6 Correct 514 ms 58112 KB Output is correct
7 Correct 522 ms 51620 KB Output is correct
8 Correct 1083 ms 51796 KB Output is correct
9 Incorrect 575 ms 51260 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 478 ms 51380 KB Output is correct
3 Correct 1894 ms 51284 KB Output is correct
4 Correct 1950 ms 51316 KB Output is correct
5 Execution timed out 2029 ms 51368 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 64880 KB Output is correct
2 Correct 1091 ms 64792 KB Output is correct
3 Correct 716 ms 64228 KB Output is correct
4 Correct 700 ms 64164 KB Output is correct
5 Correct 830 ms 61004 KB Output is correct
6 Correct 973 ms 61008 KB Output is correct
7 Correct 882 ms 59476 KB Output is correct
8 Correct 810 ms 59380 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18920 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 4 ms 18776 KB Output is correct
7 Correct 3 ms 19032 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 4 ms 18868 KB Output is correct
10 Correct 4 ms 18780 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Incorrect 3 ms 18780 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18920 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 4 ms 18776 KB Output is correct
7 Correct 3 ms 19032 KB Output is correct
8 Correct 4 ms 19032 KB Output is correct
9 Correct 4 ms 18868 KB Output is correct
10 Correct 4 ms 18780 KB Output is correct
11 Correct 3 ms 18780 KB Output is correct
12 Incorrect 3 ms 18780 KB Output isn't correct
13 Halted 0 ms 0 KB -