Submission #1003489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003489		underwaterkillerwhale	Sequence (APIO23_sequence)	C++17	35 / 100	360 ms	15188 KiB

sequence

#ifdef ONLINE_JUDGE
    #include "cyberland.h"
#endif

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 5e5 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const ll INF = 1e18;
const int BASE = 137;

int n;
int a[N];

namespace sub2 {
    vector<int> vec;
    int numVal;
    int cnt[N];

    struct fenwick_Tree {
        int Range;
        int fen[N];
        void init (int n) {
            Range = n;
            rep (i, 1, Range) fen[i] = 0;
        }
        void update (int pos, int val) {
            for (; pos <= Range; pos += pos & -pos) fen[pos] += val;
        }
        int get (int pos) {
            int res = 0;
            for (; pos > 0; pos -= pos & -pos)  res += fen[pos];
            return res;
        }
    }BIT;

    void compress() {
        rep (i, 1, n) vec.push_back(a[i]);
        sort (ALL(vec));
        vec.resize (numVal = unique(ALL(vec)) - vec.begin());
    }

    int solution() {
        compress();
        int res = 0;
        rep (i, 1, n) {
            BIT.init(numVal);
            rep (v, 1, numVal) cnt[v] = 0;
            rep (j, i, n) {
                int nval = lower_bound(ALL(vec), a[j]) - vec.begin() + 1;
                BIT.update(nval, 1);
                cnt[nval]++;
                int pos1; {
                    int lf = 1, rt = numVal;
                    while (lf < rt) {
                        int mid = lf + rt >> 1;
                        if (BIT.get(mid) - 1 >= floor(1.0 * (j - i) /2)) rt = mid;
                        else lf = mid + 1;
                    }
                    pos1 = lf;
                }
                int pos2; {
                    int lf = 1, rt = numVal;
                    while (lf < rt) {
                        int mid = lf + rt >> 1;
                        if (BIT.get(mid) - 1 >= ceil(1.0 * (j - i) /2)) rt = mid;
                        else lf = mid + 1;
                    }
                    pos2 = lf;
                }
//                cout << i <<" "<<j<<" "<<pos1 <<" "<<pos2 <<"\n";
                res = max({res, cnt[pos1], cnt[pos2]});
            }
        }
        return res;
    }
}

namespace sub3 {
    bool check () {
        rep (i, 1, n) if (a[i] > a[i + 1]) {
            rep (j, i + 1, n) if (a[j] < a[j + 1]) return 0;
        }
        return 1;
    }

    int cnt[N];
    int R[N], L[N];

    int solution() {
        rep (i ,1, n) cnt[a[i]]++;
        rep (i, 1, n) if (L[a[i]] == 0) L[a[i]] = i;
        reb (i, n, 1) if (R[a[i]] == 0) R[a[i]] = i;
        int res = 0;
        rep (i, 1, n) {
            int pos = i;
            while (a[i] == a[i + 1]) ++i;
            res = max(res, i - pos + 1);
        }
        rep (i, 1, n) {
            int val = a[i];
            if (R[val] - L[val] + 1 == cnt[val]) continue;
            int smaller = (n - R[val] + L[val] - 1), bigger = R[val] - L[val] + 1 - cnt[val];
            if (smaller >= bigger) res = max(res, cnt[val]);
            else if (bigger - smaller <= cnt[val]) res = max(res, cnt[val]);
        }
        return res;

    }
}
int sequence (int _n, vector<int> A) {
    n = _n;
    rep (i, 1, n) a[i] = A[i - 1];
    if (n <= 3000)
        return sub2 :: solution();
    else if (sub3 :: check())
        return sub3 :: solution();
}
//void solution() {
//    cin >> n;
//    rep (i, 1, n) cin >> a[i];
//    if (n <= 3000)
//        cout << sub2 :: solution() <<"\n";
//    else
//        if (sub3 :: check())
//        cout << sub3 :: solution() <<"\n";
////    else cout << sub160907 :: solution() <<"\n";
//}
//
//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
//int main () {
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
////    file ("c");
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}

/*
7
1 2 3 1 2 1 3
1
4 4 30
3
1 1 2 1
0 1 5
0 2 5
1 3 2
2 3 4


3 2
0 1 5
0 2 5
1
1 2

*/

Compilation message (stderr)

sequence.cpp: In function 'int sub2::solution()':
sequence.cpp:75:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |                         int mid = lf + rt >> 1;
      |                                   ~~~^~~~
sequence.cpp:84:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |                         int mid = lf + rt >> 1;
      |                                   ~~~^~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:137:1: warning: control reaches end of non-void function [-Wreturn-type]
  137 | }
      | ^

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