| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 982333 | davitmarg | 서열 (APIO23_sequence) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#include <fstream>
#define fastIO \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 500005;
int n, a[N], ans = 1;
vector<int> pos[N];
pair<int, int> merge(pair<int, int> a, pair<int, int> b)
{
return MP(min(a.first, b.first), max(a.second, b.second));
}
struct Node {
Node* left = nullptr;
Node* right = nullptr;
pair<int, int> minmax;
int lazy = 0;
Node(Node* l, Node* r, pair<int, int> mm)
{
left = l;
right = r;
minmax = mm;
}
};
Node* build(int start, int end) {
if (start == end) {
return new Node(nullptr, nullptr, MP(start, start));
}
int mid = start + (end - start) / 2;
Node* leftChild = build(start, mid);
Node* rightChild = build(mid + 1, end);
return new Node(leftChild, rightChild, merge(leftChild->minmax, rightChild->minmax));
}
void propagate(Node* node, int start, int end) {
if (node->lazy != 0) {
node->minmax.first += node->lazy;
node->minmax.second += node->lazy;
if (start != end) {
node->left = new Node(*node->left);
node->right = new Node(*node->right);
node->left->lazy += node->lazy;
node->right->lazy += node->lazy;
}
node->lazy = 0;
}
}
Node* update(Node* node, int start, int end, int l, int r, int val) {
propagate(node, start, end);
if (r < start || end < l) {
return node; // No overlap
}
if (l <= start && end <= r) {
Node* newNode = new Node(*node);
newNode->lazy += val;
propagate(newNode, start, end);
return newNode;
}
int mid = start + (end - start) / 2;
Node* leftChild = update(node->left, start, mid, l, r, val);
Node* rightChild = update(node->right, mid + 1, end, l, r, val);
return new Node(leftChild, rightChild, merge(leftChild->minmax, rightChild->minmax));
}
pair<int, int> query(Node* node, int start, int end, int l, int r) {
propagate(node, start, end);
if (r < start || end < l) {
return { INT_MAX, INT_MIN };
}
if (l <= start && end <= r) {
return node->minmax;
}
int mid = start + (end - start) / 2;
pair<int, int> leftRes = query(node->left, start, mid, l, r);
pair<int, int> rightRes = query(node->right, mid + 1, end, l, r);
return { min(leftRes.first, rightRes.first), max(leftRes.second, rightRes.second) };
}
bool check(int x, int k, int p, Node* n1, Node* n2)
{
int i = pos[x][p];
int j = pos[x][k];
int len = p - k + 1;
pair<int, int> dr = query(n1, 0, n, i, n);
dr.first -= len;
dr.second -= len;
pair<int, int> dl = query(n1, 0, n, 0, j - 1);
pair<int, int> d = MP(dr.first - dl.second, dr.second - dl.first);
pair<int, int> dr2 = query(n2, 0, n, i, n);
dr2.first += len;
dr2.second += len;
pair<int, int> dl2 = query(n2, 0, n, 0, j - 1);
pair<int, int> d2 = MP(dr2.first - dl2.second, dr2.second - dl2.first);
return ((d.second < 0 && len >= -d.second) || (d.first > 0 && len >= d.first) || (d.first <= 0 && d.second >= 0) || (d2.second < 0 && len >= -d2.second) || (d2.first > 0 && len >= d2.first) || (d2.first <= 0 && d2.second >= 0));
}
bool check(int x, int len, Node* n1, Node* n2)
{
for (int p = len - 1; p < pos[x].size(); p++)
if (check(x, p - len + 1, p, n1, n2))
return true;
return false;
}
int sequence(int nn, vector<int> aa)
{
n = nn;
for (int i = 1; i <= n; i++)
a[i] = aa[i - 1];
for (int i = 1; i <= n; i++)
pos[a[i]].push_back(i);
Node* t = build(0, n);
for (int x = 1; x <= n; x++)
{
Node* n1 = t;
Node* n2 = t;
for (int p = 0; p < pos[x].size(); p++)
{
int i = pos[x][p];
n2 = update(n2, 0, n, i, n, -2);
}
int l = ans, r = pos[x].size();
while (l <= r)
{
int m = (l + r) / 2;
if (check(x, m, n1, n2))
{
ans = max(ans, m);
l = m + 1;
}
else
r = m - 1;
}
t = n2;
}
return ans;
}
#ifdef death
void solve()
{
int nn;
vector<int> aa;
cin >> nn;
for (int i = 0; i < nn; i++)
{
int x;
cin >> x;
aa.push_back(x);
}
cout << sequence(nn, aa) << endl;
}
int main()
{
fastIO;
int T = 1;
//cin >> T;
while (T--)
solve();
return 0;
}
#endif // death
/*
7
1 2 3 1 2 1 3
9
1 1 2 3 4 3 2 1 1
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
*/