Submission #852078

#	Time	Username	Problem	Language	Result	Execution time	Memory
852078		mychecksedad	Sequence (APIO23_sequence)	C++17	100 / 100	835 ms	47356 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) {
    return {min(a.first, b.first), max(a.second, b.second)};
}

constexpr int inf = 1e9 + 7;

constexpr pair<int, int> neutral{inf, -inf};

namespace SegmentTree {
    constexpr int N_ = 1 << 20;
    pair<int, int> t[N_];
    int tag[N_];
    int sz = 1;

    void init(int n) {
        sz = 1 << __lg(n) + !!(n & (n - 1));
        fill(t, t + sz * 2, neutral);
        fill(tag, tag + sz * 2, 0);
        for (int i = 0; i < n; ++i) {
            t[i + sz].first = t[i + sz].second = i;
        }
        for (int i = sz - 1; i > 0; --i) {
            t[i] = t[i << 1] + t[i << 1 | 1];
        }
    }

    void rangeAdd(int l, int r, int d, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return;
        }
        if (l <= lx && rx <= r) {
            t[x].first += d;
            t[x].second += d;
            tag[x] += d;
            return;
        }
        int mid = lx + rx >> 1;
        rangeAdd(l, r, d, x << 1, lx, mid), rangeAdd(l, r, d, x << 1 | 1, mid, rx);
        t[x] = t[x << 1] + t[x << 1 | 1];
        t[x].first += tag[x], t[x].second += tag[x];
    }

    pair<int, int> rangeSum(int l, int r, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return neutral;
        }
        if (l <= lx && rx <= r) {
            return t[x];
        }
        int mid = lx + rx >> 1;
        pair<int, int> res = rangeSum(l, r, x << 1, lx, mid) + rangeSum(l, r, x << 1 | 1, mid, rx);
        res.first += tag[x], res.second += tag[x];
        return res;
    }
}


int sequence(int n, std::vector<int> a) {
    vector<vector<int>> adj(n);

    for (int i = 0; i < n; ++i) {
        adj[--a[i]].push_back(i);
    }

    int ans = 1;

    SegmentTree::init(n + 1);

    for (int x = 0; x < n; ++x) {
        for (int i : adj[x]) {
            SegmentTree::rangeAdd(i + 1, n + 1, -2);
        }
        for (int i = int(size(adj[x])) - 1; i >= 0; --i) {
            SegmentTree::rangeAdd(adj[x][i] + 1, n + 1, 2);
            pair<int, int> resL = SegmentTree::rangeSum(0, adj[x][i] + 1);

            while (i + ans < size(adj[x])) {
                int r = i + ans;
                pair<int, int> resR = SegmentTree::rangeSum(adj[x][r] + 1, n + 1);
                resR.first -= 2 * (ans + 1);

                if (max(resL.first, resR.first) <= min(resL.second, resR.second)) {
                    ans += 1;
                } else {
                    break;
                }
            }
        }
        for (int i : adj[x]) {
            SegmentTree::rangeAdd(i + 1, n + 1, -2);
        }
    }

    return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'void SegmentTree::init(int)':
sequence.cpp:21:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   21 |         sz = 1 << __lg(n) + !!(n & (n - 1));
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'void SegmentTree::rangeAdd(int, int, int, int, int, int)':
sequence.cpp:42:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
sequence.cpp: In function 'std::pair<int, int> SegmentTree::rangeSum(int, int, int, int, int)':
sequence.cpp:55:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:82:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             while (i + ans < size(adj[x])) {
      |                    ~~~~~~~~^~~~~~~~~~~~~~

• 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