oj.uz

Submission #751738

# Submission time Handle Problem Language Result Execution time Memory
751738 2023-06-01T10:57:27 Z Desh03 Sequence (APIO23_sequence) C++17
40 / 100
 2000 ms 1757300 KB 
#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 SegmentTree {
    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;
            }
        }
    } *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

sequence.cpp: In constructor 'SegmentTree::node::node()':
sequence.cpp:12:20: warning: 'SegmentTree::node::d' will be initialized after [-Wreorder]
   12 |         int mn, h, d, delta;
      |                    ^
sequence.cpp:12:13: warning:   'int SegmentTree::node::mn' [-Wreorder]
   12 |         int mn, h, d, delta;
      |             ^~
sequence.cpp:14:9: warning:   when initialized here [-Wreorder]
   14 |         node() : h(0), d(0), mn(0), delta(0), left(NULL), right(NULL) { };
      |         ^~~~
sequence.cpp: In member function 'void SegmentTree::node::push(int, int)':
sequence.cpp:19:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |             int m = l + r >> 1;
      |                     ~~^~~
sequence.cpp: In member function 'void SegmentTree::upd(SegmentTree::node*&, int, int, int, int, int, int)':
sequence.cpp:58:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int m = l + r >> 1;
      |                 ~~^~~
sequence.cpp: In member function 'void SegmentTree::upd2(SegmentTree::node*&, int, int, int, int, int)':
sequence.cpp:72:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int m = l + r >> 1;
      |                 ~~^~~
sequence.cpp: In member function 'int SegmentTree::find_first(SegmentTree::node*&, int, int, int)':
sequence.cpp:80:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int m = l + r >> 1;
      |                 ~~^~~
sequence.cpp: In member function 'int SegmentTree::qry(SegmentTree::node*&, int, int, int)':
sequence.cpp:87:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int m = l + r >> 1;
      |                 ~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15828 KB Output is correct
3 Correct 7 ms 15844 KB Output is correct
4 Correct 7 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15916 KB Output is correct
7 Correct 8 ms 15852 KB Output is correct
8 Correct 8 ms 15916 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 7 ms 15884 KB Output is correct
12 Correct 10 ms 15956 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15828 KB Output is correct
3 Correct 7 ms 15844 KB Output is correct
4 Correct 7 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15916 KB Output is correct
7 Correct 8 ms 15852 KB Output is correct
8 Correct 8 ms 15916 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 7 ms 15884 KB Output is correct
12 Correct 10 ms 15956 KB Output is correct
13 Correct 547 ms 16084 KB Output is correct
14 Correct 526 ms 16084 KB Output is correct
15 Correct 572 ms 16212 KB Output is correct
16 Correct 529 ms 16084 KB Output is correct
17 Correct 517 ms 16084 KB Output is correct
18 Correct 478 ms 16088 KB Output is correct
19 Correct 554 ms 16084 KB Output is correct
20 Correct 539 ms 16088 KB Output is correct
21 Correct 542 ms 16084 KB Output is correct
22 Correct 534 ms 16084 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Execution timed out 2170 ms 1398268 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15828 KB Output is correct
2 Correct 915 ms 279420 KB Output is correct
3 Correct 924 ms 305724 KB Output is correct
4 Correct 929 ms 305696 KB Output is correct
5 Correct 951 ms 279496 KB Output is correct
6 Correct 865 ms 254588 KB Output is correct

Subtask #5
0.0 / 13.0

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

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15828 KB Output is correct
3 Correct 7 ms 15844 KB Output is correct
4 Correct 7 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15916 KB Output is correct
7 Correct 8 ms 15852 KB Output is correct
8 Correct 8 ms 15916 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 7 ms 15884 KB Output is correct
12 Correct 10 ms 15956 KB Output is correct
13 Correct 547 ms 16084 KB Output is correct
14 Correct 526 ms 16084 KB Output is correct
15 Correct 572 ms 16212 KB Output is correct
16 Correct 529 ms 16084 KB Output is correct
17 Correct 517 ms 16084 KB Output is correct
18 Correct 478 ms 16088 KB Output is correct
19 Correct 554 ms 16084 KB Output is correct
20 Correct 539 ms 16088 KB Output is correct
21 Correct 542 ms 16084 KB Output is correct
22 Correct 534 ms 16084 KB Output is correct
23 Incorrect 475 ms 280252 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15828 KB Output is correct
3 Correct 7 ms 15844 KB Output is correct
4 Correct 7 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15916 KB Output is correct
7 Correct 8 ms 15852 KB Output is correct
8 Correct 8 ms 15916 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 7 ms 15884 KB Output is correct
12 Correct 10 ms 15956 KB Output is correct
13 Correct 547 ms 16084 KB Output is correct
14 Correct 526 ms 16084 KB Output is correct
15 Correct 572 ms 16212 KB Output is correct
16 Correct 529 ms 16084 KB Output is correct
17 Correct 517 ms 16084 KB Output is correct
18 Correct 478 ms 16088 KB Output is correct
19 Correct 554 ms 16084 KB Output is correct
20 Correct 539 ms 16088 KB Output is correct
21 Correct 542 ms 16084 KB Output is correct
22 Correct 534 ms 16084 KB Output is correct
23 Execution timed out 2170 ms 1398268 KB Time limit exceeded
24 Halted 0 ms 0 KB -