Submission #981320

#	Time	Username	Problem	Language	Result	Execution time	Memory
981320		math_rabbit_1028	Sequence (APIO23_sequence)	C++17	20 / 100	1419 ms	73260 KiB

sequence

#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[2020202];
    int lazy[2020202];

    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) {
    int s = pos[t][i], e = pos[t][j]; // [0, 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 (s > e) {
                e++;
                continue;
            }
            if (can(t, s, e)) {
                ans = max(ans, e-s+1);
                e++;
            }
            else s++;
        }
    }

    return ans;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 7 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18