oj.uz

Submission #981386

# Submission time Handle Problem Language Result Execution time Memory
981386 2024-05-13T06:46:36 Z math_rabbit_1028 Sequence (APIO23_sequence) C++17
0 / 100
 2000 ms 57668 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);
        }

        for (int s = 0; s < pos[t].size(); s++) {
            int st = s, ed = pos[t].size()-1;
            while (st < ed) {
                int mid = (st+ed+1)/2;
                if (can(t, s, mid)) {
                    ans = max(ans, mid-s+1);
                    st = mid;
                }
                else ed = mid-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:126:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for (int s = 0; s < pos[t].size(); s++) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31836 KB Output is correct
2 Correct 6 ms 31836 KB Output is correct
3 Correct 6 ms 31836 KB Output is correct
4 Correct 6 ms 31920 KB Output is correct
5 Correct 6 ms 31836 KB Output is correct
6 Incorrect 6 ms 31836 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31836 KB Output is correct
2 Correct 6 ms 31836 KB Output is correct
3 Correct 6 ms 31836 KB Output is correct
4 Correct 6 ms 31920 KB Output is correct
5 Correct 6 ms 31836 KB Output is correct
6 Incorrect 6 ms 31836 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31836 KB Output is correct
2 Correct 871 ms 52048 KB Output is correct
3 Correct 914 ms 51812 KB Output is correct
4 Execution timed out 2054 ms 43740 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 2052 ms 44032 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 841 ms 57668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31836 KB Output is correct
2 Correct 6 ms 31836 KB Output is correct
3 Correct 6 ms 31836 KB Output is correct
4 Correct 6 ms 31920 KB Output is correct
5 Correct 6 ms 31836 KB Output is correct
6 Incorrect 6 ms 31836 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31836 KB Output is correct
2 Correct 6 ms 31836 KB Output is correct
3 Correct 6 ms 31836 KB Output is correct
4 Correct 6 ms 31920 KB Output is correct
5 Correct 6 ms 31836 KB Output is correct
6 Incorrect 6 ms 31836 KB Output isn't correct
7 Halted 0 ms 0 KB -