제출 #874582

#제출 시각아이디문제언어결과실행 시간메모리
874582Stickfish서열 (APIO23_sequence)C++17
0 / 100
1668 ms67312 KiB
#include "sequence.h" #include <iostream> #include <vector> using namespace std; inline bool in(pair<int, int> sg, int x) { return sg.first <= x && x <= sg.second; } inline bool intersect(pair<int, int> sg1, pair<int, int> sg2) { return in(sg1, sg2.first) || in(sg2, sg1.first); } inline int distance(pair<int, int> sg1, pair<int, int> sg2) { if (intersect(sg1, sg2)) return 0; if (sg1.first > sg2.first) return sg1.first - sg2.second; return sg2.first - sg1.second; } int get_ans(vector<pair<int, int>> a) { int n = a.size(); vector<pair<int, int>> cova(n); cova[n - 1].first = a[n - 1].first - (n - 1); cova[n - 1].second = a[n - 1].second + (n - 1); for (int i = n - 2; i >= 0; --i) { cova[i].first = min(cova[i + 1].first, a[i].first - i); cova[i].second = max(cova[i + 1].second, a[i].second + i); } int ans = 0; for (int l = 0; l < n; ++l) { int lb = l + ans; int ub = n; while (ub - lb > 1) { int mb = (lb + ub) / 2; pair<int, int> sg = cova[mb]; sg.first += l; sg.second -= l; //cout << l << ' ' << r << ": " << "(" << sg.first << ' ' << sg.second << ") " << if (intersect(a[l], sg)) { lb = mb; } else { ub = mb; } } ans = lb - l; } return ans; } struct stree { void resize(int n) { sz = n; mod.resize(2 * n); mn.resize(2 * n); mx.resize(2 * n); } void add(int l, int r, int x) { //cout << "OHOH " << l << ' ' << r << endl;; //for (int i = l; i < r; ++i) //mod[i] += x; //return; add(0, 0, sz, l, r, x); } int get_min(int l, int r) { //cout << "HOHO " << l << ' ' << r << endl;; //int ans = 1000000; //for (int i = l; i < r; ++i) //ans = min(ans, mod[i]); //return ans; return get_min(0, 0, sz, l, r); } int get_max(int l, int r) { //cout << "HAHA " << l << ' ' << r << endl;; //int ans = -1000000; //for (int i = l; i < r; ++i) //ans = max(ans, mod[i]); //return ans; return get_max(0, 0, sz, l, r); } private: int sz; vector<int> mod; vector<int> mn; vector<int> mx; void add(int ind, int lnd, int rnd, int l, int r, int x) { if (l <= lnd && rnd <= r) { mod[ind] += x; mn[ind] += x; mx[ind] += x; return; } if (lnd >= r || l >= rnd) return; int mnd = (lnd + rnd) / 2; int chd = ind + (mnd - lnd) * 2; add(ind + 1, lnd, mnd, l, r, x); add(chd, mnd, rnd, l, r, x); mn[ind] = min(mn[ind + 1], mn[chd]) + mod[ind]; mx[ind] = max(mx[ind + 1], mx[chd]) + mod[ind]; } int get_max(int ind, int lnd, int rnd, int l, int r) { if (l <= lnd && rnd <= r) { return mx[ind]; } if (lnd >= r || l >= rnd) return -10000000; int mnd = (lnd + rnd) / 2; int chd = ind + (mnd - lnd) * 2; return max(get_max(ind + 1, lnd, mnd, l, r), get_max(chd, mnd, rnd, l, r)) + mod[ind]; } int get_min(int ind, int lnd, int rnd, int l, int r) { if (l <= lnd && rnd <= r) { return mn[ind]; } if (lnd >= r || l >= rnd) return 10000000; int mnd = (lnd + rnd) / 2; int chd = ind + (mnd - lnd) * 2; return min(get_min(ind + 1, lnd, mnd, l, r), get_min(chd, mnd, rnd, l, r)) + mod[ind]; } }; int sequence(int N, vector<int> A) { vector<vector<int>> ra(N + 1); for (int i = 0; i < N; ++i) { ra[A[i]].push_back(i); } stree tr; tr.resize(N); for (int i = 0; i < N; ++i) { tr.add(i, N, 1); } int ans = 0; for (int x = 1; x <= N; ++x) { if (ra[x].empty()) continue; //vector<pair<int, int>> p; //int pval = 0; //int cpmx = 0; //int cpmn = 0; //for (int i = 0; i < N; ++i) { //if (A[i] == x) { //p.push_back({cpmn, cpmx}); //cpmx = cpmn = pval; //} else if (A[i] < x) { //--pval; //cpmn = min(cpmn, pval); //} else { //++pval; //cpmx = max(cpmx, pval); //} //} //p.push_back({cpmn, cpmx}); for (auto i : ra[x]) tr.add(i, N, -1); vector<pair<int, int>> p; ra[x].insert(ra[x].begin(), 0); ra[x].push_back(N - 1); //for (int i = 0; i < N; ++i) //cout << tr.get_min(i, i + 1) << ' '; //cout << endl; for (size_t i = 0; i + 1 < ra[x].size(); ++i) { int l = ra[x][i]; int r = ra[x][i + 1] + 1; p.push_back({tr.get_min(l, r), tr.get_max(l, r)}); } ra[x].pop_back(); ra[x].erase(ra[x].begin()); p[0].first = min(p[0].first, 0); p[0].second = max(p[0].second, 0); cout << x << ": "; for (auto x : p) cout << "(" << x.first << ' ' << x.second << ") "; cout << get_ans(p) << endl; ans = max(ans, get_ans(p)); for (auto i : ra[x]) tr.add(i, N, -1); } return ans; }
#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...