oj.uz

답안 #947018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
947018 2024-03-15T10:32:51 Z Nhoksocqt1 서열 (APIO23_sequence) C++17
47 / 100
 1434 ms 16904 KB 
#ifndef Nhoksocqt1
    #include "sequence.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 500005;

int fen[2 * MAXN], fenp[2 * MAXN];
int val[MAXN], cnt[MAXN], nArr;

int sub2(void) {
    int res(1);
    for (int l = 1; l <= nArr; ++l) {
        set<int> Set;
        int pos(val[l]), cntPos(1);
        Set.insert(pos);
        ++cnt[pos];

        for (int r = l + 1; r <= nArr; ++r) {
            cntPos += (val[r] <= pos);
            if(++cnt[val[r]] == 1)
                Set.insert(val[r]);

            while(cntPos < (r - l + 1) / 2 + 1) {
                auto it = Set.lower_bound(pos); ++it;
                assert(it != Set.end());
                pos = *it;
                cntPos += cnt[pos];
            }

            while(cntPos - cnt[pos] >= (r - l + 1) / 2 + 1) {
                cntPos -= cnt[pos];
                auto it = Set.lower_bound(pos);
                assert(it != Set.begin()); --it;
                pos = *it;
            }

            //cout << l << ' ' << r << ' ' << pos << ' ' << cntPos << '\n';
            res = max(res, cnt[pos]);
            if((r - l + 1) % 2 == 0 && cntPos - cnt[pos] >= (r - l + 1) / 2) {
                auto it = Set.lower_bound(pos);
                assert(it != Set.begin()); --it;
                res = max(res, cnt[*it]);
            }
        }

        for (int r = l; r <= nArr; ++r)
            --cnt[val[r]];
    }

    return res;
}

int sub3(void) {
    int res(0);
    for (int i = 1; i <= nArr; ) {
        int j(i);
        while(j <= nArr && val[j] == val[i])
            ++j;

        res = max(res, j - i);
        i = j;
    }

    for (int i = 1; i <= nArr; ++i)
        ++cnt[val[i]];

    int j(nArr);
    for (int i = 1; i <= j; ++i) {
        if(i > 1 && val[i] == val[i - 1])
            continue;

        while(j > i && val[j] < val[i])
            --cnt[val[j--]];

        if(j > i && val[i] == val[j]) {
            int cntPos = cnt[val[i]];
            if(cnt[val[i]] + i - 1 + nArr - j >= (nArr + 1) / 2)
                res = max(res, cnt[val[i]]);
        }
    }

    return res;
}

void modify(int fen[], int i, int v) {
    for (i += nArr + 1; i <= 2 * nArr + 1; i += i & -i)
        fen[i] += v;
}

int get(int fen[], int i) {
    int res(0);
    for (i += nArr + 1; i > 0; i -= i & -i)
        res += fen[i];

    return res;
}

bool check4(int minCnt, int x) {
    for (int i = 1; i <= 2 * nArr; ++i)
        fen[i] = fenp[i] = 0;

    ll res(0);
    int j(1), cnt(0), sumx(0), sumpx(0), sumxj(0), sumpxj(0);
    for (int i = 1; i <= nArr; ++i) {
        cnt += (val[i] == x);
        while(j <= i && cnt >= minCnt) {
            cnt -= (val[j] == x);
            modify(fen, sumxj, +1);
            modify(fenp, sumpxj, +1);
            sumxj += 2 * (val[j] <= x) - 1;
            sumpxj += 2 * (val[j] < x) - 1;
            ++j;
        }

        sumx += 2 * (val[i] <= x) - 1;
        sumpx += 2 * (val[i] < x) - 1;
        res += get(fen, sumx) - get(fenp, sumpx);
    }

    return (res > 0);
}

int sub4(void) {
    int res(1);
    for (int i = 1; i <= 3; ++i) {
        int l(2), r(nArr);
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(check4(mid, i)) {
                res = max(res, mid);
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }

    return res;
}

int sequence(int _N, vector<int> _A) {
    nArr = _N;
    for (int i = 1; i <= nArr; ++i)
        val[i] = _A[i - 1];

    bool check3(1);
    for (int i = 1; i <= nArr; ++i) {
        check3 &= (i <= 2 || val[i - 2] <= val[i - 1] || val[i - 2] >= val[i - 1] && val[i - 1] >= val[i]);
    }

    if(nArr <= 2000) {
        return sub2();
    } else
        if(check3) {
            return sub3();
        } else
            if(*max_element(val + 1, val + nArr + 1) <= 3) {
                return sub4();
            }
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "sequence"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> _A;
    int _N;
    cin >> _N;

    _A.resize(_N);
    for (int i = 0; i < _N; ++i) {
        cin >> _A[i];
        //_A[i] = Random(1, 3); cout << _A[i] << " \n"[i + 1 == _N];
    }

    int ans = sequence(_N, _A);
    cout << "ANSWER: " << ans << '\n';

    return 0;
}

#endif // Nhoksocqt1

Compilation message

sequence.cpp: In function 'int sub3()':
sequence.cpp:95:17: warning: unused variable 'cntPos' [-Wunused-variable]
   95 |             int cntPos = cnt[val[i]];
      |                 ^~~~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:167:83: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  167 |         check3 &= (i <= 2 || val[i - 2] <= val[i - 1] || val[i - 2] >= val[i - 1] && val[i - 1] >= val[i]);
      |                                                          ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:179:1: warning: control reaches end of non-void function [-Wreturn-type]
  179 | }
      | ^

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 219 ms 2556 KB Output is correct
14 Correct 201 ms 2556 KB Output is correct
15 Correct 22 ms 2396 KB Output is correct
16 Correct 22 ms 2396 KB Output is correct
17 Correct 9 ms 2392 KB Output is correct
18 Correct 199 ms 2644 KB Output is correct
19 Correct 170 ms 2392 KB Output is correct
20 Correct 144 ms 2548 KB Output is correct
21 Correct 186 ms 2640 KB Output is correct
22 Correct 198 ms 2392 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 39 ms 8528 KB Output is correct
3 Correct 40 ms 8548 KB Output is correct
4 Correct 32 ms 8276 KB Output is correct
5 Correct 39 ms 8624 KB Output is correct
6 Correct 51 ms 8788 KB Output is correct
7 Correct 33 ms 8272 KB Output is correct
8 Correct 33 ms 8452 KB Output is correct
9 Correct 33 ms 8276 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1349 ms 15920 KB Output is correct
3 Correct 1434 ms 15920 KB Output is correct
4 Correct 1426 ms 16724 KB Output is correct
5 Correct 1329 ms 16900 KB Output is correct
6 Correct 706 ms 16904 KB Output is correct

Subtask #5
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 463 ms 15916 KB Output is correct
2 Correct 470 ms 15920 KB Output is correct
3 Incorrect 464 ms 15916 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 219 ms 2556 KB Output is correct
14 Correct 201 ms 2556 KB Output is correct
15 Correct 22 ms 2396 KB Output is correct
16 Correct 22 ms 2396 KB Output is correct
17 Correct 9 ms 2392 KB Output is correct
18 Correct 199 ms 2644 KB Output is correct
19 Correct 170 ms 2392 KB Output is correct
20 Correct 144 ms 2548 KB Output is correct
21 Correct 186 ms 2640 KB Output is correct
22 Correct 198 ms 2392 KB Output is correct
23 Incorrect 61 ms 11352 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 219 ms 2556 KB Output is correct
14 Correct 201 ms 2556 KB Output is correct
15 Correct 22 ms 2396 KB Output is correct
16 Correct 22 ms 2396 KB Output is correct
17 Correct 9 ms 2392 KB Output is correct
18 Correct 199 ms 2644 KB Output is correct
19 Correct 170 ms 2392 KB Output is correct
20 Correct 144 ms 2548 KB Output is correct
21 Correct 186 ms 2640 KB Output is correct
22 Correct 198 ms 2392 KB Output is correct
23 Correct 39 ms 8528 KB Output is correct
24 Correct 40 ms 8548 KB Output is correct
25 Correct 32 ms 8276 KB Output is correct
26 Correct 39 ms 8624 KB Output is correct
27 Correct 51 ms 8788 KB Output is correct
28 Correct 33 ms 8272 KB Output is correct
29 Correct 33 ms 8452 KB Output is correct
30 Correct 33 ms 8276 KB Output is correct
31 Correct 1349 ms 15920 KB Output is correct
32 Correct 1434 ms 15920 KB Output is correct
33 Correct 1426 ms 16724 KB Output is correct
34 Correct 1329 ms 16900 KB Output is correct
35 Correct 706 ms 16904 KB Output is correct
36 Correct 463 ms 15916 KB Output is correct
37 Correct 470 ms 15920 KB Output is correct
38 Incorrect 464 ms 15916 KB Output isn't correct
39 Halted 0 ms 0 KB -