Submission #751743

#	Time	Username	Problem	Language	Result	Execution time	Memory
751743		Desh03	Sequence (APIO23_sequence)	C++17	40 / 100	2159 ms	1561512 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct node {
    int mn, h, d, delta;
    node *left, *right;
    node() : h(0), d(0), mn(0), delta(0), left(NULL), right(NULL) { };
    void pull() {
        mn = min(left->mn, right->mn);
    }
    void push(int l, int r) {
        int m = l + r >> 1;
        if (left == NULL) left = new node();
        if (right == NULL) right = new node();
        if (h != -1) {
            left->h = h;
            left->d = d;
            right->h = h + (m - l + 1) * d;
            right->d = d;
            if (d > 0) {
                left->mn = left->h;
                right->mn = right->h;
            } else {
                left->mn = h + (m - l) * d;
                right->mn = h + (r - l) * d;
            }
            h = -1;
            delta = 0;
        }
        if (delta) {
            left->mn += delta;
            if (left->h != -1) left->h += delta;
            else left->delta += delta;
            right->mn += delta;
            if (right->h != -1) right->h += delta;
            else right->delta += delta;
            delta = 0;
        }
    }
};

struct SegmentTree {
    node *root;
    int n;
    void upd(node* &v, int l, int r, int ql, int qr, int h, int d) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            v->delta = 0;
            v->h = h + (l - ql + 1) * d, v->d = d;
            v->mn = d > 0 ? v->h : v->h + (r - l) * d;
            return;
        }
        v->push(l, r);
        int m = l + r >> 1;
        upd(v->left, l, m, ql, qr, h, d);
        upd(v->right, m + 1, r, ql, qr, h, d);
        v->pull();
    }
    void upd2(node* &v, int l, int r, int ql, int qr, int delta) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            v->mn += delta;
            if (v->h != -1) v->h += delta;
            else v->delta += delta;
            return;
        }
        v->push(l, r);
        int m = l + r >> 1;
        upd2(v->left, l, m, ql, qr, delta);
        upd2(v->right, m + 1, r, ql, qr, delta);
        v->pull();
    }
    int find_first(node* &v, int l, int r, int h) {
        if (l == r) return l;
        v->push(l, r);
        int m = l + r >> 1;
        if (v->left->mn < h) return find_first(v->left, l, m, h);
        return find_first(v->right, m + 1, r, h);
    }
    int qry(node* &v, int l, int r, int u) {
        if (l == r) return v->mn;
        v->push(l, r);
        int m = l + r >> 1;
        if (u <= m) return qry(v->left, l, m, u);
        return qry(v->right, m + 1, r, u);
    }
    SegmentTree() : root(NULL) { };
    SegmentTree(int n_) : root(new node()), n(n_) { }; // Declares an array of size n with initial elements zero, zero-based indexing.
    int qry(int u) { // Returns the element at index u.
        if (u < 0 || u > n - 1) return 0;
        return qry(root, 0, n - 1, u);
    }
    int find_first(int h) { // Returns the index of the first element < h in the array, or -1 if no such element exists.
        if (root->mn >= h) return -1;
        return find_first(root, 0, n - 1, h);
    }
    void upd(int l, int r, int h, int d) { // Assigns an arithmetic progression h + id to elements in range [l, r], i = 1, 2, 3, ..., r - l + 1.
        if (l > r) return;
        upd(root, 0, n - 1, l, r, h, d);
    }
    void upd2(int l, int r, int delta) { // Adds delta to elements in range [l, r].
        if (l > r) return;
        upd2(root, 0, n - 1, l, r, delta);
    }
} s[500000], pre[500000];

int sequence(int n, vector<int> a) {
    int ans = 0;
    if (n <= 3e3) {
        oset<pair<int, int>> s;
        vector<int> f(n + 1);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                s.insert({a[j], j});
                ++f[a[j]];
                int med1 = (*s.find_by_order((j - i) / 2)).first, med2 = (*s.find_by_order((j - i + 1) / 2)).first;
                ans = max(ans, max(f[med1], f[med2]));
            }
            s.clear();
            f = vector<int> (n + 1);
        }
        return ans;
    } else {
        for (int i = 0; i < n; i++) s[i] = SegmentTree(n), pre[i] = SegmentTree(n);
        for (int i = 0; i < n; i++) s[i].upd(0, n - 1, 1, -1);
        for (int i = 0; i < n; i++) {
            --a[i];
            pre[a[i]].upd2(i, n - 1, 1);
            s[a[i]].upd(i, i, 2 * pre[a[i]].qry(i - 1) - i + 1, -1);
            s[a[i]].upd(i + 1, n - 1, 2 * pre[a[i]].qry(i) - i, -1);
        }
        for (int i = 0; i < n; i++) {
            int l = s[a[i]].find_first(2 * pre[a[i]].qry(i) - i);
            if (l == -1 || l > i) continue;
            ans = max(ans, pre[a[i]].qry(i) - pre[a[i]].qry(l - 1));
        }
        sort(a.begin(), a.end());
        return max(ans, (a[n >> 1] == 1 || a[(n - 1) >> 1] == 1 ? pre[1].qry(n - 1) : 0));
    }
}

Compilation message (stderr)

sequence.cpp: In constructor 'node::node()':
sequence.cpp:11:16: warning: 'node::d' will be initialized after [-Wreorder]
   11 |     int mn, h, d, delta;
      |                ^
sequence.cpp:11:9: warning:   'int node::mn' [-Wreorder]
   11 |     int mn, h, d, delta;
      |         ^~
sequence.cpp:13:5: warning:   when initialized here [-Wreorder]
   13 |     node() : h(0), d(0), mn(0), delta(0), left(NULL), right(NULL) { };
      |     ^~~~
sequence.cpp: In member function 'void node::push(int, int)':
sequence.cpp:18:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |         int m = l + r >> 1;
      |                 ~~^~~
sequence.cpp: In member function 'void SegmentTree::upd(node*&, int, int, int, int, int, int)':
sequence.cpp:60:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int m = l + r >> 1;
      |                 ~~^~~
sequence.cpp: In member function 'void SegmentTree::upd2(node*&, int, int, int, int, int)':
sequence.cpp:74:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int m = l + r >> 1;
      |                 ~~^~~
sequence.cpp: In member function 'int SegmentTree::find_first(node*&, int, int, int)':
sequence.cpp:82:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |         int m = l + r >> 1;
      |                 ~~^~~
sequence.cpp: In member function 'int SegmentTree::qry(node*&, int, int, int)':
sequence.cpp:89:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         int m = l + r >> 1;
      |                 ~~^~~

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