Submission #947017

#TimeUsernameProblemLanguageResultExecution timeMemory
947017Nhoksocqt1Sequence (APIO23_sequence)C++17
35 / 100
1536 ms19416 KiB
#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 - (val[j] == x) >= 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]; int ans = sequence(_N, _A); cout << "ANSWER: " << ans << '\n'; return 0; } #endif // Nhoksocqt1

Compilation message (stderr)

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 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...