#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 time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1668 ms |
67312 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
