| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1228294 | Dzadzo | 서열 (APIO23_sequence) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "sequence.h"
#define ll long long
// #define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF 1000000000000000
#define MOD 1000000007
#define MAXN 200000
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//
//
// struct LazySegTree {
// struct Node { int mn, mx, add; Node(): mn(INT_MAX), mx(INT_MIN), add(0) {} };
// int n;
// vector<Node> st;
//
// LazySegTree(int _n): n(_n) { st.resize(4*(n+1)); }
//
// void build(int p, int l, int r, const vector<int>& a) {
// if (l == r) { st[p].mn = st[p].mx = a[l]; return; }
// int m = (l + r) >> 1;
// build(p<<1, l, m, a);
// build(p<<1|1, m+1, r, a);
// pull(p);
// }
//
// void pull(int p) {
// st[p].mn = min(st[p<<1].mn, st[p<<1|1].mn);
// st[p].mx = max(st[p<<1].mx, st[p<<1|1].mx);
// }
//
// void apply(int p, int v) {
// st[p].mn += v;
// st[p].mx += v;
// st[p].add += v;
// }
//
// void push(int p) {
// if (st[p].add) {
// apply(p<<1, st[p].add);
// apply(p<<1|1, st[p].add);
// st[p].add = 0;
// }
// }
//
// void update(int p, int l, int r, int i, int j, int v) {
// if (j < l || r < i) return;
// if (i <= l && r <= j) { apply(p, v); return; }
// push(p);
// int m = (l + r) >> 1;
// update(p<<1, l, m, i, j, v);
// update(p<<1|1, m+1, r, i, j, v);
// pull(p);
// }
//
// int queryMin(int p, int l, int r, int i, int j) {
// if (j < l || r < i) return INT_MAX;
// if (i <= l && r <= j) return st[p].mn;
// push(p);
// int m = (l + r) >> 1;
// return min({queryMin(p<<1, l, m, i, j), queryMin(p<<1|1, m+1, r, i, j)});
// }
//
// int queryMax(int p, int l, int r, int i, int j) {
// if (j < l || r < i) return INT_MIN;
// if (i <= l && r <= j) return st[p].mx;
// push(p);
// int m = (l + r) >> 1;
// return max({queryMax(p<<1, l, m, i, j), queryMax(p<<1|1, m+1, r, i, j)});
// }
//
// void build(const vector<int>& a) { build(1, 1, n, a); }
// void Add(int l, int r, int v) { update(1, 1, n, l, r, v); }
// int Min(int l, int r) { return queryMin(1, 1, n, l, r); }
// int Max(int l, int r) { return queryMax(1, 1, n, l, r); }
// };
//
//
// int sequence(int n, vi a) {
// vvi Q(n+1);
// reverse(a.begin(), a.end());
// a.pb(0);
// reverse(a.begin(), a.end());
// for (int i=1;i<=n;i++)Q[a[i]].pb(i);
//
//
// LazySegTree pmax(n),pmin(n);
//
//
// pmax.build(vi(n+1,0));
// pmin.build(vi(n+1,0));
//
// for (int i=1;i<=n;i++)pmin.Add(i,n,1),pmax.Add(i,n,1);
// int res=1;
// for (int i=1;i<=n;i++) {
//
// for (int x:Q[i]) {
// pmax.Add(x,n,-1);
// pmin.Add(x,n,-1);
// }
//
// vi prefmin(Q[i].size()),prefmax(Q[i].size()),suffmin(Q[i].size()),suffmax(Q[i].size());
//
// for (int j=0;j<Q[i].size();j++) {
// int idx=Q[i][j];
//
// if (idx>1) {
// prefmin[j]=pmin.Min(1,idx-1);
// prefmax[j]=pmax.Max(1,idx-1);
// }
// // for (int z=1;z<=n;z++)cout<<pmax.Max(z,z)<<" ";cout<<'\n';
// // for (int z=1;z<=n;z++)cout<<pmin.Max(z,z)<<" ";cout<<'\n';
// // cout<<'\n';
// pmin.Add(1,idx,-1);
// pmax.Add(1,idx,1);
//
//
// }
//
// for (int j=0;j<Q[i].size();j++) {
//
// int idx=Q[i][j];
//
// pmin.Add(1,idx,1);
// pmax.Add(1,idx,-1);
// }
//
// for (int j=Q[i].size()-1;j>=0;j--) {
//
// int idx=Q[i][j];
//
// suffmin[j]=pmin.Min(idx,n);
// suffmax[j]=pmax.Max(idx,n);
//
// pmin.Add(idx,n,-1);
// pmax.Add(idx,n,1);
//
// }
//
// for (int j=Q[i].size()-1;j>=0;j--) {
//
// int idx=Q[i][j];
// pmin.Add(idx,n,1);
// pmax.Add(idx,n,-1);
//
// }
//
// for (int x:Q[i])pmin.Add(x,n,-1),pmax.Add(x,n,-1);
//
// int L=0;
// for (int R=0;R<Q[i].size();R++) {
// // cout<<prefmin[R]<<" "<<prefmax[R]<<'\n';
// // cout<<suffmin[R]<<" "<<suffmax[R]<<'\n';
// while (L < R && ( suffmax[R]-prefmin[L] < - ( R - L + 1 ) || suffmin[R]-prefmax[L] > ( R - L + 1 ) ) )L++;
//
// // cout<<L<<" "<<R<<'\n';
// // cout<<'\n';
// res=max(res,R-L+1);
//
// }
//
// }
// return res;
//
// }
int sequence(int N, const vector<int>& A) {
int ans = 0;
// Enumerate all subarrays [l..r]
for (int l = 0; l < N; ++l) {
for (int r = l; r < N; ++r) {
// Extract and sort the subarray A[l..r]
vector<int> B;
B.reserve(r - l + 1);
for (int i = l; i <= r; ++i)
B.push_back(A[i]);
sort(B.begin(), B.end()); // O(k log k), k = r-l+1
int k = B.size();
// Find the median set S
vector<int> medians;
if (k % 2 == 1) {
medians.push_back(B[k/2]);
} else {
medians.push_back(B[k/2 - 1]);
medians.push_back(B[k/2]);
}
// For each median x, count W(l,r,x) by scanning A[l..r]
for (int x : medians) {
int cnt = 0;
for (int i = l; i <= r; ++i)
if (A[i] == x) ++cnt;
ans = max(ans, cnt);
}
}
}
return ans;
}
// int main() {
// cout<<sequence(10, {2,3,1,1,3,3,3,3,1,3});
// }
/*
*/