oj.uz

Submission #980782

# Submission time Handle Problem Language Result Execution time Memory
980782 2024-05-12T11:42:32 Z davitmarg Sequence (APIO23_sequence) C++17
41 / 100
 2000 ms 49120 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;
vector<int> pos[N];
pair<int, int> t[N * 4];
int d[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)
    );
}




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


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


        for (int p = 0; p < pos[x].size(); p++)
        {
            int i = pos[x][p];
            for (int k = p - ans; k >= 0; k--)
            {
                int j = pos[x][k];
                int len = p - k + 1;

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


                if ((d.second < 0 && len >= -d.second) || (d.first > 0 && len >= d.first) || (d.first <= 0 && d.second >= 0))
                    ans = max(ans, len);
            }
        }


        for (int p = 0; p < pos[x].size(); p++)
        {
            int i = pos[x][p];
            add(1, 0, n, i, n, -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

/*

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:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for (int p = 0; p < pos[x].size(); p++)
      |                         ~~^~~~~~~~~~~~~~~
sequence.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for (int p = 0; p < pos[x].size(); p++)
      |                         ~~^~~~~~~~~~~~~~~
sequence.cpp:135:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for (int p = 0; p < pos[x].size(); p++)
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16832 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 4 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 5 ms 16732 KB Output is correct
14 Correct 5 ms 16732 KB Output is correct
15 Correct 8 ms 16728 KB Output is correct
16 Correct 9 ms 16728 KB Output is correct
17 Correct 39 ms 16728 KB Output is correct
18 Correct 4 ms 16732 KB Output is correct
19 Correct 5 ms 16732 KB Output is correct
20 Correct 5 ms 16732 KB Output is correct
21 Correct 15 ms 16920 KB Output is correct
22 Correct 12 ms 16732 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 401 ms 43256 KB Output is correct
3 Correct 402 ms 43244 KB Output is correct
4 Execution timed out 2060 ms 35280 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 468 ms 35324 KB Output is correct
3 Execution timed out 2057 ms 35464 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 48720 KB Output is correct
2 Correct 521 ms 49120 KB Output is correct
3 Correct 583 ms 48500 KB Output is correct
4 Correct 514 ms 48212 KB Output is correct
5 Correct 491 ms 44976 KB Output is correct
6 Correct 508 ms 45136 KB Output is correct
7 Correct 457 ms 43856 KB Output is correct
8 Correct 431 ms 43856 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16832 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 4 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 5 ms 16732 KB Output is correct
14 Correct 5 ms 16732 KB Output is correct
15 Correct 8 ms 16728 KB Output is correct
16 Correct 9 ms 16728 KB Output is correct
17 Correct 39 ms 16728 KB Output is correct
18 Correct 4 ms 16732 KB Output is correct
19 Correct 5 ms 16732 KB Output is correct
20 Correct 5 ms 16732 KB Output is correct
21 Correct 15 ms 16920 KB Output is correct
22 Correct 12 ms 16732 KB Output is correct
23 Correct 80 ms 22096 KB Output is correct
24 Correct 77 ms 22108 KB Output is correct
25 Correct 80 ms 22352 KB Output is correct
26 Correct 1800 ms 21236 KB Output is correct
27 Correct 1802 ms 21236 KB Output is correct
28 Correct 1832 ms 21228 KB Output is correct
29 Execution timed out 2052 ms 20852 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16832 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 4 ms 16732 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 5 ms 16732 KB Output is correct
14 Correct 5 ms 16732 KB Output is correct
15 Correct 8 ms 16728 KB Output is correct
16 Correct 9 ms 16728 KB Output is correct
17 Correct 39 ms 16728 KB Output is correct
18 Correct 4 ms 16732 KB Output is correct
19 Correct 5 ms 16732 KB Output is correct
20 Correct 5 ms 16732 KB Output is correct
21 Correct 15 ms 16920 KB Output is correct
22 Correct 12 ms 16732 KB Output is correct
23 Correct 401 ms 43256 KB Output is correct
24 Correct 402 ms 43244 KB Output is correct
25 Execution timed out 2060 ms 35280 KB Time limit exceeded
26 Halted 0 ms 0 KB -