Submission #1070343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070343		thangdz2k7	Sequence (APIO23_sequence)	C++17	100 / 100	616 ms	52320 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

vector <int> pos[N];
int mn[4 * N], mx[4 * N], lz[4 * N];

void build(int s, int l, int r){
    if (l == r){
        mn[s] = l;
        mx[s] = l;
        return;
    }
    int mid = l + r >> 1;
    build(2 * s, l, mid);
    build(2 * s + 1, mid + 1, r);
    mn[s] = min(mn[2 * s], mn[2 * s + 1]) + lz[s];
    mx[s] = max(mx[2 * s], mx[2 * s + 1]) + lz[s];
}

void upd(int s, int l, int r, int u, int v, int val){
    if (u <= l && r <= v){
        mn[s] += val;
        mx[s] += val;
        lz[s] += val;
        return;
    }

    int mid = l + r >> 1;
    if (mid >= u) upd(2 * s, l, mid, u, v, val);
    if (mid + 1 <= v) upd(2 * s + 1, mid + 1, r, u, v, val);
    mn[s] = min(mn[2 * s], mn[2 * s + 1]) + lz[s];
    mx[s] = max(mx[2 * s], mx[2 * s + 1]) + lz[s];
}

int getMin(int s, int l, int r, int u, int v){
    if (r < u || l > v) return 1e9;
    if (u <= l && r <= v) return mn[s];
    int mid = l + r >> 1;
    return min(getMin(2 * s, l, mid, u, v), getMin(2 * s + 1, mid + 1, r, u, v)) + lz[s];
}

int getMax(int s, int l, int r, int u, int v){
    if (r < u || l > v) return -1e9;
    if (u <= l && r <= v) return mx[s];
    int mid = l + r >> 1;
    return max(getMax(2 * s, l, mid, u, v), getMax(2 * s + 1, mid + 1, r, u, v)) + lz[s];
}

int sequence(int n, vector <int> a){
    for (int i = 0; i < n; ++ i) pos[a[i]].push_back(i + 1);
    build(1, 0, n);

    int res = 1;
    for (int i = 1; i <= n; ++ i){
        vector <int> mx_sf, mn_pf;
        for (int j : pos[i]){
            mx_sf.push_back(getMax(1, 0, n, j, n));
            mn_pf.push_back(getMin(1, 0, n, 0, j - 1));
        }
        for (int j : pos[i]) upd(1, 0, n, j, n, -2);
        vector <int> mn_sf, mx_pf;
        for (int j : pos[i]){
            mn_sf.push_back(getMin(1, 0, n, j, n));
            mx_pf.push_back(getMax(1, 0, n, 0, j - 1));
        }

        for (int j = pos[i].size() - 1; j >= 0; -- j){
            while (j + res < pos[i].size()){
                if (mn_pf[j] <= mx_sf[j + res] && mn_sf[j + res] <= mx_pf[j]) ++ res;
                else break;
            }
        }
    }

    return res;
}

Compilation message (stderr)

sequence.cpp: In function 'void build(int, int, int)':
sequence.cpp:16:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     int mid = l + r >> 1;
      |               ~~^~~
sequence.cpp: In function 'void upd(int, int, int, int, int, int)':
sequence.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid = l + r >> 1;
      |               ~~^~~
sequence.cpp: In function 'int getMin(int, int, int, int, int)':
sequence.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid = l + r >> 1;
      |               ~~^~~
sequence.cpp: In function 'int getMax(int, int, int, int, int)':
sequence.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = l + r >> 1;
      |               ~~^~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:71:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             while (j + res < pos[i].size()){
      |                    ~~~~~~~~^~~~~~~~~~~~~~~

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