oj.uz

Submission #1003489

# Submission time Handle Problem Language Result Execution time Memory
1003489 2024-06-20T11:51:14 Z underwaterkillerwhale Sequence (APIO23_sequence) C++17
35 / 100
 360 ms 15188 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) 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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 456 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 456 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 275 ms 348 KB Output is correct
14 Correct 288 ms 348 KB Output is correct
15 Correct 104 ms 344 KB Output is correct
16 Correct 99 ms 348 KB Output is correct
17 Correct 30 ms 344 KB Output is correct
18 Correct 360 ms 348 KB Output is correct
19 Correct 273 ms 604 KB Output is correct
20 Correct 224 ms 348 KB Output is correct
21 Correct 244 ms 600 KB Output is correct
22 Correct 248 ms 500 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 42 ms 14928 KB Output is correct
3 Correct 50 ms 14928 KB Output is correct
4 Correct 27 ms 7132 KB Output is correct
5 Correct 42 ms 15188 KB Output is correct
6 Correct 41 ms 15188 KB Output is correct
7 Correct 27 ms 7500 KB Output is correct
8 Correct 27 ms 7504 KB Output is correct
9 Correct 38 ms 7120 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 30 ms 7248 KB Output is correct
3 Incorrect 27 ms 7136 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 14932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 456 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 275 ms 348 KB Output is correct
14 Correct 288 ms 348 KB Output is correct
15 Correct 104 ms 344 KB Output is correct
16 Correct 99 ms 348 KB Output is correct
17 Correct 30 ms 344 KB Output is correct
18 Correct 360 ms 348 KB Output is correct
19 Correct 273 ms 604 KB Output is correct
20 Correct 224 ms 348 KB Output is correct
21 Correct 244 ms 600 KB Output is correct
22 Correct 248 ms 500 KB Output is correct
23 Incorrect 7 ms 2652 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 456 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 275 ms 348 KB Output is correct
14 Correct 288 ms 348 KB Output is correct
15 Correct 104 ms 344 KB Output is correct
16 Correct 99 ms 348 KB Output is correct
17 Correct 30 ms 344 KB Output is correct
18 Correct 360 ms 348 KB Output is correct
19 Correct 273 ms 604 KB Output is correct
20 Correct 224 ms 348 KB Output is correct
21 Correct 244 ms 600 KB Output is correct
22 Correct 248 ms 500 KB Output is correct
23 Correct 42 ms 14928 KB Output is correct
24 Correct 50 ms 14928 KB Output is correct
25 Correct 27 ms 7132 KB Output is correct
26 Correct 42 ms 15188 KB Output is correct
27 Correct 41 ms 15188 KB Output is correct
28 Correct 27 ms 7500 KB Output is correct
29 Correct 27 ms 7504 KB Output is correct
30 Correct 38 ms 7120 KB Output is correct
31 Correct 30 ms 7248 KB Output is correct
32 Incorrect 27 ms 7136 KB Output isn't correct
33 Halted 0 ms 0 KB -