| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1038074 | pan | 서열 (APIO23_sequence) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include <bits/stdc++.h>
#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i)
#define RFOR(i, x, n) for (ll i =x; i>=n; --i)
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;
// Condition for median: -c <= h - l <= c
struct node
{
int s, e, m;
ll minn, maxx;
ll lazy;
node *l, *r;
node (int S, int E)
{
s = S, e = E, m = (s+e)/2;
minn = s, maxx = e;
lazy = 0;
l=r=nullptr;
}
void create()
{
if(s != e && l==nullptr)
{
l = new node(s, m);
r = new node(m+1, e);
}
}
void propogate()
{
if (lazy==0) return;
create();
minn+=lazy;
maxx += lazy;
if (s != e){
l->lazy+=lazy;
r->lazy+=lazy;
}
lazy=0;
}
void update(int S, int E, ll V)
{
propogate();
if(s==S && e==E) lazy += V;
else{
create();
if(E <= m) l->update(S, E, V);
else if (m < S) r->update(S, E, V);
else l->update(S, m, V),r->update(m+1, E, V);
l->propogate(),r->propogate();
maxx = max(l->maxx, r->maxx);
minn = min(l->minn, r->minn);
}
}
pi query(int S, int E)
{
if (S> E) return mp(0LL, 0LL);
propogate();
if(s == S && e == E) return mp(minn, maxx);
create();
if(E <= m) return l->query(S, E);
else if(S >= m+1) return r->query(S, E);
else
{
pi a = l->query(S, m), b = r->query(m+1, E);
return mp(min(a.f, b.f), max(a.s, b.s));
}
}
} *root;
vector<ll> dis[500005];
int sequence(int N, std::vector<int> A)
{
ll n = N;
ll ans = 0;
for (ll i=0; i<n; ++i) dis[A[i]].pb(i+1);
root = new node(0, n);
for (ll i=1; i<=n; ++i)
{
for (ll u: dis[i]) root->update(u, n, -1);
ll N = dis[i].size();
ll r = 0;
for (ll l=0; l<N; ++l)
{
ll st = ((l==0)?0:dis[i][l-1]);
while (r < N)
{
ll ee = ((r==N-1)?n:dis[i][r+1]-1);
ll len = r-l+1;
pi l1 = root->query(st, dis[i][l]-1), r1 = root->query(dis[i][r], ee);
ll maxx = r1.f - l1.s;
ll minn = r1.s - l1.f;
if (maxx <= len && minn >= -len) {ans = max(ans, len); r++;}
else break;
}
}
for (ll u: dis[i]) root->update(u, n, -1);
}
return ans;
}