oj.uz

Submission #751743

# Submission time Handle Problem Language Result Execution time Memory
751743 2023-06-01T11:07:58 Z Desh03 Sequence (APIO23_sequence) C++17
40 / 100
 2000 ms 1561512 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 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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15936 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 11 ms 15952 KB Output is correct
5 Correct 8 ms 15956 KB Output is correct
6 Correct 8 ms 15872 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15864 KB Output is correct
9 Correct 8 ms 15956 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 9 ms 15860 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 15936 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 11 ms 15952 KB Output is correct
5 Correct 8 ms 15956 KB Output is correct
6 Correct 8 ms 15872 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15864 KB Output is correct
9 Correct 8 ms 15956 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 9 ms 15860 KB Output is correct
12 Correct 10 ms 15956 KB Output is correct
13 Correct 535 ms 16084 KB Output is correct
14 Correct 538 ms 16076 KB Output is correct
15 Correct 560 ms 16084 KB Output is correct
16 Correct 576 ms 16084 KB Output is correct
17 Correct 545 ms 16084 KB Output is correct
18 Correct 508 ms 16084 KB Output is correct
19 Correct 545 ms 16332 KB Output is correct
20 Correct 566 ms 16204 KB Output is correct
21 Correct 550 ms 16204 KB Output is correct
22 Correct 553 ms 16208 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15936 KB Output is correct
2 Correct 1871 ms 1399376 KB Output is correct
3 Execution timed out 2137 ms 1561512 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 950 ms 279436 KB Output is correct
3 Correct 970 ms 305760 KB Output is correct
4 Correct 989 ms 305640 KB Output is correct
5 Correct 930 ms 279472 KB Output is correct
6 Correct 969 ms 254592 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2159 ms 1472000 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 15936 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 11 ms 15952 KB Output is correct
5 Correct 8 ms 15956 KB Output is correct
6 Correct 8 ms 15872 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15864 KB Output is correct
9 Correct 8 ms 15956 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 9 ms 15860 KB Output is correct
12 Correct 10 ms 15956 KB Output is correct
13 Correct 535 ms 16084 KB Output is correct
14 Correct 538 ms 16076 KB Output is correct
15 Correct 560 ms 16084 KB Output is correct
16 Correct 576 ms 16084 KB Output is correct
17 Correct 545 ms 16084 KB Output is correct
18 Correct 508 ms 16084 KB Output is correct
19 Correct 545 ms 16332 KB Output is correct
20 Correct 566 ms 16204 KB Output is correct
21 Correct 550 ms 16204 KB Output is correct
22 Correct 553 ms 16208 KB Output is correct
23 Incorrect 504 ms 280168 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 15936 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 11 ms 15952 KB Output is correct
5 Correct 8 ms 15956 KB Output is correct
6 Correct 8 ms 15872 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15864 KB Output is correct
9 Correct 8 ms 15956 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 9 ms 15860 KB Output is correct
12 Correct 10 ms 15956 KB Output is correct
13 Correct 535 ms 16084 KB Output is correct
14 Correct 538 ms 16076 KB Output is correct
15 Correct 560 ms 16084 KB Output is correct
16 Correct 576 ms 16084 KB Output is correct
17 Correct 545 ms 16084 KB Output is correct
18 Correct 508 ms 16084 KB Output is correct
19 Correct 545 ms 16332 KB Output is correct
20 Correct 566 ms 16204 KB Output is correct
21 Correct 550 ms 16204 KB Output is correct
22 Correct 553 ms 16208 KB Output is correct
23 Correct 1871 ms 1399376 KB Output is correct
24 Execution timed out 2137 ms 1561512 KB Time limit exceeded
25 Halted 0 ms 0 KB -