Submission #982336

#	Time	Username	Problem	Language	Result	Execution time	Memory
982336		davitmarg	Sequence (APIO23_sequence)	C++17	57 / 100	2192 ms	1853260 KiB

sequence

#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> merge(pair<int, int>& a, pair<int, int>& b)
{
    return MP(min(a.first, b.first), max(a.second, b.second));
}


struct Node {
    Node* left = nullptr;
    Node* right = nullptr;
    pair<int, int> minmax;
    int lazy = 0; 

    Node(Node* l, Node* r, pair<int, int> mm)
    {
        left = l;
        right = r;
        minmax = mm;
    }

};

Node* build(int start, int end) {
    if (start == end) {
        return new Node(nullptr, nullptr, MP(start, start));
    }
    int mid = start + (end - start) / 2;
    Node* leftChild = build(start, mid);
    Node* rightChild = build(mid + 1, end);
    return new Node(leftChild, rightChild, merge(leftChild->minmax, rightChild->minmax));
}

void propagate(Node* node, int start, int end) {
    if (node->lazy != 0) {
        node->minmax.first += node->lazy;
        node->minmax.second += node->lazy;
        if (start != end) {
            node->left = new Node(*node->left); 
            node->right = new Node(*node->right);
            node->left->lazy += node->lazy;
            node->right->lazy += node->lazy;
        }
        node->lazy = 0;
    }
}

Node* update(Node* node, int start, int end, int l, int r, int val) {
    propagate(node, start, end);
    if (r < start || end < l) {
        return node; // No overlap
    }
    if (l <= start && end <= r) {
        Node* newNode = new Node(*node);
        newNode->lazy += val;
        propagate(newNode, start, end);
        return newNode;
    }
    int mid = start + (end - start) / 2;
    Node* leftChild = update(node->left, start, mid, l, r, val);
    Node* rightChild = update(node->right, mid + 1, end, l, r, val);
    return new Node(leftChild, rightChild, merge(leftChild->minmax, rightChild->minmax));
}

pair<int, int> query(Node* node, int start, int end, int l, int r) {
    propagate(node, start, end);
    if (r < start || end < l) {
        return { mod, -mod};
    }
    if (l <= start && end <= r) {
        return node->minmax;
    }
    int mid = start + (end - start) / 2;
    pair<int, int> leftRes = query(node->left, start, mid, l, r);
    pair<int, int> rightRes = query(node->right, mid + 1, end, l, r);
    return { min(leftRes.first, rightRes.first), max(leftRes.second, rightRes.second) };
}

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

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

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


    pair<int, int> dr2 = query(n2, 0, n, i, n);
    dr2.first += len;
    dr2.second += len;
    pair<int, int> dl2 = query(n2, 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, Node* n1, Node* n2)
{
    for (int p = len - 1; p < pos[x].size(); p++)
        if (check(x, p - len + 1, p, n1, n2))
            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);

    Node* t = build(0, n);

    for (int x = 1; x <= n; x++)
    {
        Node* n1 = t;
        Node* n2 = t;
        for (int p = 0; p < pos[x].size(); p++)
        {
            int i = pos[x][p];
            n2 = update(n2, 0, n, i, n, -2);
        }

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

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

        t = n2;
    }


    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 (stderr)

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

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 22 / 22
• Subtask 7: 0 / 18