oj.uz

Submission #1003488

# Submission time Handle Problem Language Result Execution time Memory
1003488 2024-06-20T11:50:29 Z underwaterkillerwhale Sequence (APIO23_sequence) C++17
28 / 100
 367 ms 14932 KB 
#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) if (L[a[i]] == 0) L[a[i]] = i, cnt[a[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

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:136:1: warning: control reaches end of non-void function [-Wreturn-type]
  136 | }
      | ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 298 ms 500 KB Output is correct
14 Correct 280 ms 344 KB Output is correct
15 Correct 111 ms 344 KB Output is correct
16 Correct 107 ms 492 KB Output is correct
17 Correct 39 ms 492 KB Output is correct
18 Correct 367 ms 344 KB Output is correct
19 Correct 238 ms 348 KB Output is correct
20 Correct 235 ms 504 KB Output is correct
21 Correct 293 ms 348 KB Output is correct
22 Correct 258 ms 344 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 40 ms 14928 KB Output is correct
3 Incorrect 50 ms 14828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Incorrect 28 ms 7248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14932 KB Output is correct
2 Correct 36 ms 14800 KB Output is correct
3 Incorrect 44 ms 14672 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 298 ms 500 KB Output is correct
14 Correct 280 ms 344 KB Output is correct
15 Correct 111 ms 344 KB Output is correct
16 Correct 107 ms 492 KB Output is correct
17 Correct 39 ms 492 KB Output is correct
18 Correct 367 ms 344 KB Output is correct
19 Correct 238 ms 348 KB Output is correct
20 Correct 235 ms 504 KB Output is correct
21 Correct 293 ms 348 KB Output is correct
22 Correct 258 ms 344 KB Output is correct
23 Incorrect 7 ms 2688 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 298 ms 500 KB Output is correct
14 Correct 280 ms 344 KB Output is correct
15 Correct 111 ms 344 KB Output is correct
16 Correct 107 ms 492 KB Output is correct
17 Correct 39 ms 492 KB Output is correct
18 Correct 367 ms 344 KB Output is correct
19 Correct 238 ms 348 KB Output is correct
20 Correct 235 ms 504 KB Output is correct
21 Correct 293 ms 348 KB Output is correct
22 Correct 258 ms 344 KB Output is correct
23 Correct 40 ms 14928 KB Output is correct
24 Incorrect 50 ms 14828 KB Output isn't correct
25 Halted 0 ms 0 KB -