oj.uz

Submission #981383

# Submission time Handle Problem Language Result Execution time Memory
981383 2024-05-13T06:42:01 Z math_rabbit_1028 Sequence (APIO23_sequence) C++17
41 / 100
 2000 ms 57748 KB 
#include "sequence.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define hi first
#define lo second

int n, m, ans = 0;
vector<int> arr, vec;
vector<int> pos[505050];

struct seg{
    pii tree[1010101];
    int lazy[1010101];

    void propa(int v, int st, int ed) {
        tree[v].hi += lazy[v];
        tree[v].lo += lazy[v];
        if (st != ed) {
            lazy[2*v] += lazy[v];
            lazy[2*v+1] += lazy[v];
        }
        lazy[v] = 0;
    }
    
    void update(int v, int st, int ed, int lt, int rt, int val) {
        propa(v, st, ed);
        if (ed < lt || st > rt) return;
        if (lt <= st && ed <= rt) {
            lazy[v] = val;
            propa(v, st, ed);
            return;
        }
        int mid = (st+ed)/2;
        update(2*v, st, mid, lt, rt, val);
        update(2*v+1, mid+1, ed, lt, rt, val);
        tree[v].hi = max(tree[2*v].hi, tree[2*v+1].hi);
        tree[v].lo = min(tree[2*v].lo, tree[2*v +1].lo);
    }

    pii merge(pii L, pii R) {
        return {max(L.hi, R.hi), min(L.lo, R.lo)};
    }

    pii get(int v, int st, int ed, int lt, int rt) {
        propa(v, st, ed);
        if (ed < lt || st > rt) return {-1e9, +1e9}; // (hi, lo)
        if (lt <= st && ed <= rt) return tree[v];
        int mid = (st+ed)/2;
        return merge(
            get(2*v, st, mid, lt, rt),
            get(2*v+1, mid+1, ed, lt, rt)
        );
    }
} evn, odd;

void upd(int i, int val) {
    evn.update(1, 0, (n-1)/2, (i+1)/2, (n-1)/2, val); // i <= 2k
    odd.update(1, 0, (n-2)/2, i/2, (n-2)/2, val); // i <= 2k+1
}

int dis(pii A, pii B) {
    if (A.lo > A.hi) return 1e9;
    if (B.lo > B.hi) return 1e9;
    if (A.hi < B.lo) return B.lo - A.hi;
    else if (B.hi < A.lo) return A.lo - B.hi;
    else return 0;
}

/* =================================================================
    -1 : a
    0 : b
    1 : c

    합 짝수(2k  ) => -b <= c-a <= b
    합 홀수(2k+1) => -(b-1) <= c-a <= b-1

    >>> |누적합| <= b - (n%2)
================================================================= */
bool can(int t, int i, int j) {
    if (i > j) return true;

    int s = pos[t][i], e = pos[t][j]; // [-1, s-1], [e, n-1]
    int b = j-i+1;

    pii evn1 = evn.get(1, 0, (n-1)/2, 0, s == 0 ? -1 : (s-1)/2);
    pii evn2 = evn.get(1, 0, (n-1)/2, (e+1)/2, (n-1)/2);
    pii odd1 = odd.merge({0, 0}, odd.get(1, 0, (n-2)/2, 0, s <= 1 ? -1 : (s-2)/2));
    pii odd2 = odd.get(1, 0, (n-2)/2, e/2, (n-2)/2);

    if (dis(evn1, evn2) <= b) return true; // 짝 짝
    if (dis(evn1, odd2) <= b-1) return true; // 짝 홀
    if (dis(odd1, evn2) <= b-1) return true; // 홀 짝
    if (dis(odd1, odd2) <= b) return true; // 홀 홀
    return false;
}

int sequence(int N, vector<int> A) {
    n = N;
    arr = A;
    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());
    m = A.size();
    for (int i = 0; i < n; i++) {
        arr[i] = lower_bound(A.begin(), A.end(), arr[i]) - A.begin();
    }

    for (int i = 0; i < n; i++) {
        pos[arr[i]].push_back(i);
    }

    for (int t = 0; t < m; t++) {
        if (t == 0) {
            for (int i = 0; i < n; i++) {
                if (t == arr[i]) upd(i, 0);
                if (t > arr[i]) upd(i, -1);
                if (t < arr[i]) upd(i, 1);
            }
        }
        else {
            for (int i = 0; i < pos[t-1].size(); i++) upd(pos[t-1][i], -1);
            for (int i = 0; i < pos[t].size(); i++) upd(pos[t][i], -1);
        }
        
        // int s = 0, e = 0;
        // while (e < pos[t].size()) {
        //     if (can(t, s, e)) {
        //         ans = max(ans, e-s+1);
        //         e++;
        //     }
        //     else s++;
        // }

        for (int s = 0; s < pos[t].size(); s++) {
            for (int e = s; e < pos[t].size(); e++) {
                if (can(t, s, e)) ans = max(ans, e-s+1);
            }
        }
    }

    return ans;
}

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:122:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for (int i = 0; i < pos[t-1].size(); i++) upd(pos[t-1][i], -1);
      |                             ~~^~~~~~~~~~~~~~~~~
sequence.cpp:123:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             for (int i = 0; i < pos[t].size(); i++) upd(pos[t][i], -1);
      |                             ~~^~~~~~~~~~~~~~~
sequence.cpp:135:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for (int s = 0; s < pos[t].size(); s++) {
      |                         ~~^~~~~~~~~~~~~~~
sequence.cpp:136:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             for (int e = s; e < pos[t].size(); e++) {
      |                             ~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31836 KB Output is correct
2 Correct 6 ms 31836 KB Output is correct
3 Correct 7 ms 31672 KB Output is correct
4 Correct 7 ms 31836 KB Output is correct
5 Correct 6 ms 32096 KB Output is correct
6 Correct 6 ms 31836 KB Output is correct
7 Correct 7 ms 31836 KB Output is correct
8 Correct 6 ms 31836 KB Output is correct
9 Correct 7 ms 31832 KB Output is correct
10 Correct 6 ms 31836 KB Output is correct
11 Correct 6 ms 31832 KB Output is correct
12 Correct 6 ms 31708 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31836 KB Output is correct
2 Correct 6 ms 31836 KB Output is correct
3 Correct 7 ms 31672 KB Output is correct
4 Correct 7 ms 31836 KB Output is correct
5 Correct 6 ms 32096 KB Output is correct
6 Correct 6 ms 31836 KB Output is correct
7 Correct 7 ms 31836 KB Output is correct
8 Correct 6 ms 31836 KB Output is correct
9 Correct 7 ms 31832 KB Output is correct
10 Correct 6 ms 31836 KB Output is correct
11 Correct 6 ms 31832 KB Output is correct
12 Correct 6 ms 31708 KB Output is correct
13 Correct 9 ms 31836 KB Output is correct
14 Correct 9 ms 32088 KB Output is correct
15 Correct 24 ms 31832 KB Output is correct
16 Correct 24 ms 31836 KB Output is correct
17 Correct 135 ms 31932 KB Output is correct
18 Correct 9 ms 32088 KB Output is correct
19 Correct 25 ms 31836 KB Output is correct
20 Correct 34 ms 31964 KB Output is correct
21 Correct 25 ms 31836 KB Output is correct
22 Correct 22 ms 31836 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31836 KB Output is correct
2 Correct 1204 ms 51816 KB Output is correct
3 Correct 1251 ms 51804 KB Output is correct
4 Execution timed out 2027 ms 43736 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31836 KB Output is correct
2 Execution timed out 2032 ms 44096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 57540 KB Output is correct
2 Correct 1228 ms 57748 KB Output is correct
3 Correct 1204 ms 56968 KB Output is correct
4 Correct 1209 ms 56960 KB Output is correct
5 Correct 1181 ms 53840 KB Output is correct
6 Correct 1185 ms 53624 KB Output is correct
7 Correct 1134 ms 52420 KB Output is correct
8 Correct 1154 ms 52112 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31836 KB Output is correct
2 Correct 6 ms 31836 KB Output is correct
3 Correct 7 ms 31672 KB Output is correct
4 Correct 7 ms 31836 KB Output is correct
5 Correct 6 ms 32096 KB Output is correct
6 Correct 6 ms 31836 KB Output is correct
7 Correct 7 ms 31836 KB Output is correct
8 Correct 6 ms 31836 KB Output is correct
9 Correct 7 ms 31832 KB Output is correct
10 Correct 6 ms 31836 KB Output is correct
11 Correct 6 ms 31832 KB Output is correct
12 Correct 6 ms 31708 KB Output is correct
13 Correct 9 ms 31836 KB Output is correct
14 Correct 9 ms 32088 KB Output is correct
15 Correct 24 ms 31832 KB Output is correct
16 Correct 24 ms 31836 KB Output is correct
17 Correct 135 ms 31932 KB Output is correct
18 Correct 9 ms 32088 KB Output is correct
19 Correct 25 ms 31836 KB Output is correct
20 Correct 34 ms 31964 KB Output is correct
21 Correct 25 ms 31836 KB Output is correct
22 Correct 22 ms 31836 KB Output is correct
23 Correct 197 ms 36692 KB Output is correct
24 Correct 206 ms 36948 KB Output is correct
25 Correct 190 ms 36948 KB Output is correct
26 Execution timed out 2041 ms 35604 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31836 KB Output is correct
2 Correct 6 ms 31836 KB Output is correct
3 Correct 7 ms 31672 KB Output is correct
4 Correct 7 ms 31836 KB Output is correct
5 Correct 6 ms 32096 KB Output is correct
6 Correct 6 ms 31836 KB Output is correct
7 Correct 7 ms 31836 KB Output is correct
8 Correct 6 ms 31836 KB Output is correct
9 Correct 7 ms 31832 KB Output is correct
10 Correct 6 ms 31836 KB Output is correct
11 Correct 6 ms 31832 KB Output is correct
12 Correct 6 ms 31708 KB Output is correct
13 Correct 9 ms 31836 KB Output is correct
14 Correct 9 ms 32088 KB Output is correct
15 Correct 24 ms 31832 KB Output is correct
16 Correct 24 ms 31836 KB Output is correct
17 Correct 135 ms 31932 KB Output is correct
18 Correct 9 ms 32088 KB Output is correct
19 Correct 25 ms 31836 KB Output is correct
20 Correct 34 ms 31964 KB Output is correct
21 Correct 25 ms 31836 KB Output is correct
22 Correct 22 ms 31836 KB Output is correct
23 Correct 1204 ms 51816 KB Output is correct
24 Correct 1251 ms 51804 KB Output is correct
25 Execution timed out 2027 ms 43736 KB Time limit exceeded
26 Halted 0 ms 0 KB -