oj.uz

Submission #749737

# Submission time Handle Problem Language Result Execution time Memory
749737 2023-05-28T12:21:06 Z elazarkoren Sequence (APIO23_sequence) C++17
62 / 100
 2000 ms 58212 KB 
#include "sequence.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int infinity = 1e9;

struct Seg{
    int n;
    vii seg;
    vi add;
    Seg() {}
    Seg(int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n);
        add.resize(2 * n);
    }
    inline void pull(int i) {
        seg[i].x = min(seg[i << 1].x, seg[i << 1 | 1].x);
        seg[i].y = max(seg[i << 1].y, seg[i << 1 | 1].y);
    }
    inline void push(int i) {
        add[i << 1] += add[i];
        seg[i << 1].x += add[i], seg[i << 1].y += add[i];
        add[i << 1 | 1] += add[i];
        seg[i << 1 | 1].x += add[i], seg[i << 1 | 1].y += add[i];
        add[i] = 0;
    }
    void update(int a, int b, int x, int ind, int l, int r) {
        if (a <= l && r <= b) {
            add[ind] += x;
            seg[ind].x += x, seg[ind].y += x;
            return;
        }
        if (r <= a || b <= l) return;
        push(ind);
        update(a, b, x, ind << 1, l, (l + r) >> 1);
        update(a, b, x, ind << 1 | 1, (l + r) >> 1, r);
        pull(ind);
    }
    inline void update(int a, int b, int x) {
        update(a, b, x, 1, 0, n);
    }
    pii query(int a, int b, int ind, int l, int r) {
        if (a <= l && r <= b) return seg[ind];
        if (r <= a || b <= l) return {infinity, -infinity};
        push(ind);
        pii p1 = query(a, b, ind << 1, l, (l + r) >> 1);
        pii p2 = query(a, b, ind << 1 | 1, (l + r) >> 1, r);
        return {min(p1.x, p2.x), max(p1.y, p2.y)};
    }
    inline pii query(int a, int b) {
        return query(a, b, 1, 0, n);
    }
};

int sequence(int n, vi a) {
    vi vals;
    for (int x : a) vals.push_back(x);
    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(all(vals), a[i]) - vals.begin() + 1;
    }
    int siz = vals.size();
    vvi pos(siz + 1);
    Seg seg_minus(n + 1), seg_plus(n + 1);
    for (int i = 0; i < n; i++) {
        pos[a[i]].push_back(i + 1);
        seg_minus.update(i + 1, n + 1, 1);
        seg_plus.update(i + 1, n + 1, 1);
    }
    int ans = 1;
    for (int i = 1; i <= siz; i++) {
        for (int j : pos[i - 1]) {
            seg_plus.update(j, n + 1, -2);
        }
        for (int j : pos[i]) {
            seg_minus.update(j, n + 1, -2);
        }
        int sz = pos[i].size();
        vii minus_before(sz);
        vii minus_after(sz);
        vii plus_before(sz);
        vii plus_after(sz);
        for (int k = 0; k < sz; k++) {
            int j = pos[i][k];
            minus_before[k] = seg_minus.query(0, j);
            minus_after[k] = seg_minus.query(j, n + 1);
            plus_before[k] = seg_plus.query(0, j);
            plus_after[k] = seg_plus.query(j, n + 1);
        }
        int begin = ans + 1, end = sz + 1, mid;
        while (begin < end) {
            mid = (begin + end) >> 1;
            bool good = false;
            for (int ind1 = 0, ind2 = mid - 1; ind2 < pos[i].size(); ind1++, ind2++) {
                int l1 = minus_before[ind1].x, r1 = minus_before[ind1].y;
                int l2 = minus_after[ind2].x, r2 = minus_after[ind2].y;
                if (!(r1 < l2 || r2 < l1)) {
                    good = true;
                    break;
                }
                if (r2 < l1) {
                    int d = r2 - l1;
                    if (d + 2 * mid >= 0) {
                        good = true;
                        break;
                    }
                }
                l1 = plus_before[ind1].x, r1 = plus_before[ind1].y;
                l2 = plus_after[ind2].x, r2 = plus_after[ind2].y;
                if (!(r1 < l2 || r2 < l1)) {
                    good = true;
                    break;
                }
                if (r1 < l2) {
                    int d = l2 - r1;
                    if (d - 2 * mid <= 0) {
                        good = true;
                        break;
                    }
                }
            }
            if (good) begin = mid + 1;
            else end = mid;
        }
        chkmax(ans, begin - 1);
    }
    return ans;
}
/*
4
3 1 2 2
 */

/*
8
1 1 3 3 2 4 1 1
 */

Compilation message

sequence.cpp: In function 'int sequence(int, vi)':
sequence.cpp:106:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             for (int ind1 = 0, ind2 = mid - 1; ind2 < pos[i].size(); ind1++, ind2++) {
      |                                                ~~~~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 6 ms 340 KB Output is correct
16 Correct 5 ms 452 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 6 ms 468 KB Output is correct
19 Correct 5 ms 468 KB Output is correct
20 Correct 6 ms 468 KB Output is correct
21 Correct 6 ms 596 KB Output is correct
22 Correct 6 ms 444 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 2058 ms 48188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1600 ms 42176 KB Output is correct
3 Correct 1530 ms 39556 KB Output is correct
4 Correct 1786 ms 39488 KB Output is correct
5 Correct 1709 ms 42312 KB Output is correct
6 Correct 1774 ms 42184 KB Output is correct

Subtask #5
0.0 / 13.0

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

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 6 ms 340 KB Output is correct
16 Correct 5 ms 452 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 6 ms 468 KB Output is correct
19 Correct 5 ms 468 KB Output is correct
20 Correct 6 ms 468 KB Output is correct
21 Correct 6 ms 596 KB Output is correct
22 Correct 6 ms 444 KB Output is correct
23 Correct 319 ms 10308 KB Output is correct
24 Correct 259 ms 10080 KB Output is correct
25 Correct 370 ms 10196 KB Output is correct
26 Correct 285 ms 8096 KB Output is correct
27 Correct 309 ms 8072 KB Output is correct
28 Correct 297 ms 7988 KB Output is correct
29 Correct 261 ms 8436 KB Output is correct
30 Correct 270 ms 8388 KB Output is correct
31 Correct 225 ms 10272 KB Output is correct
32 Correct 229 ms 11716 KB Output is correct
33 Correct 266 ms 10112 KB Output is correct
34 Correct 305 ms 10200 KB Output is correct
35 Correct 300 ms 10112 KB Output is correct
36 Correct 306 ms 10088 KB Output is correct
37 Correct 253 ms 10088 KB Output is correct
38 Correct 326 ms 10188 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 6 ms 340 KB Output is correct
16 Correct 5 ms 452 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 6 ms 468 KB Output is correct
19 Correct 5 ms 468 KB Output is correct
20 Correct 6 ms 468 KB Output is correct
21 Correct 6 ms 596 KB Output is correct
22 Correct 6 ms 444 KB Output is correct
23 Execution timed out 2058 ms 48188 KB Time limit exceeded
24 Halted 0 ms 0 KB -