| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 985168 | Tsagana | 서열 (APIO23_sequence) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "sequence.h"
//OP
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define pi pair<int, int >
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mset multiset
#define F first
#define S second
#define meta int M = (L + R) /2, x = 2 * id + 1, y = x + 1
using namespace std;
vector<int> ct[500005];
int N;
struct segTree {
pi seg[2000005];
int lazy[2000005];
void laze(int id, int l, int r) {
if (!lazy[id]) {
seg[id] = {seg[id].F + lazy[id], seg[id].S + lazy[id]};
if (l != r) {
lazy[i*2+1] += lazy[id];
lazy[i*2+2] += lazy[id];
}
lazy[id] = 0;
}
}
void build(int id, int L, int R, int val) {
lazy[i] = 0;
if (l == r) {seg[i].F = seg[i].S = val * (l); return;}
meta;
build(x, L, M, val);
build(y, M + 1, R, val);
seg[id].F = min(seg[x].F, seg[y].F);
seg[id].S = max(seg[x].S, seg[y].S);
} void build(int val) {build(0, 0, N, val);}
void update(int id, int L, int R, int l, int r, int val) {
if (L <= l && r >= R) lazy[id] += val;
laze(id, L, R); meta;
if (l > R || r < L || (l <= L && r >= R)) return;
update(x, L, M, l, r, val);
update(y, M + 1, R, l, r, val);
seg[id].F = min(seg[x].F, seg[y].F);
seg[id].S = max(seg[x].S, seg[y].S);
} void update(int l, int r, int val) {update(0, 0, N, l + 1, r + 1, val);}
pi query(int id, int L, int R, int l, int r) {
laze(id, L, R); meta;
if (l > R || r < L) return {(int)1e9, (int)-1e9};
if (l <= L && r >= R) return seg[i];
pi q1 = query(x, l, M, l, r);
pi q2 = query(y, M + 1, R, l, r);
return {min(q1.f, q2.f), max(q1.s, q2.s)};
} pi query(int l, int r) {return query(0, 0, N, l + 1, r + 1);}
} les, mor;
int sequence(int n, vector<int> A) {
N = n;
for (int i = 0; i < N; i++) ct[A[i]].pb(i);
int ans = 1;
les.build(-1);
mor.build(1);
for (int i = 1; i <= N; i++) {
for (int j: ct[i]) les.update(j, N-1, 2);
for (int j = 0; j + ans < ct[i].size(); j++) {
int st = ct[i][j];
int en = ct[i][j+ans];
int qles = les.query(en, N-1).s - les.query(-1, st-1).F;
int qmor = mor.query(en, N-1).s - mor.query(-1, st-1).F;
if (qles >= 0 && qmor >= 0) {ans++; j--;}
}
for (int j: ct[i]) mor.update(j, N-1, -2);
}
return ans;
}
//ED