제출 #754960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
754960		Zanite	서열 (APIO23_sequence)	C++17	0 / 100	2067 ms	31592 KiB

sequence

#include "sequence.h"

// 赤コーダーになりたい
// お願い いいですか？

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// Pragmas
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
using namespace std;
using namespace __gnu_pbds;

// Data types
using si	= short int;
using ll	= long long;
using lll	= __int128;
using ld	= long double;

// Pairs
using pii	= pair<int, int>;
using psi	= pair<si, si>;
using pll	= pair<ll, ll>;
using plll	= pair<lll, lll>;
using pld	= pair<ld, ld>;
#define fi	first
#define se	second

// For
#define Frue(i, n, N)		for (int i = (n); i <= (N); i++)
#define  Fru(i, n, N)		for (int i = (n); i <  (N); i++)
#define Frde(i, n, N)		for (int i = (n); i >= (N); i--)
#define  Frd(i, n, N)		for (int i = (n); i >  (N); i--)

// PBDS
template<typename Z>
using ordered_set	= tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;

// Various outputs
template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
  return os << '(' << p.fi << ',' << p.se << ')';
}
template<typename Z> ostream& operator<<(ostream &os, const vector<Z> &v) {
  os << '{'; bool _first = 1;
  for (auto &i : v) {if (!_first) os << ", "; os << i; _first = 0;}
  return os << '}';
}
template<typename Z, unsigned long long sz> ostream& operator<<(ostream &os, const array<Z, sz> &arr) {
  os << '{'; bool _first = 1;
  for (auto &i : arr) {if (!_first) os << ", "; os << i; _first = 0;}
  return os << '}';
}

// Quick macro functions
#define sqr(x)			((x)*(x))
#define debug(x)		cout << #x << " = " << (x) << '\n'
#define debugV(v, x)	cout << #v << "[" << (x) << "] = " << (v[x]) << '\n'
#define rrebug(x)		cerr << #x << " = " << (x) << '\n'
#define rrebugV(v, x)	cerr << #v << "[" << (x) << "] = " << (v[x]) << '\n'

#define All(x)			x.begin(), x.end()
#define Sort(x)			sort(All(x))
#define Reverse(x)		reverse(All(x))
#define Uniqueify(x)	Sort(x); x.erase(unique(All(x)), x.end())

#define RandomSeed			chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases	int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)

// Check min and max
template<typename Z> void chmin(Z &a, Z b) {a = min(a, b);}
template<typename Z> void chmax(Z &a, Z b) {a = max(a, b);}
 
// Modular arithmetic
template<int MOD>
class ModInt {
  public:
  int v;
  ModInt() : v(0) {}
  ModInt(long long _v) {
    v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
    if (v < 0) v += MOD;
  }
 
  friend bool operator==(const ModInt &a, const ModInt &b) {return a.v == b.v;}
  friend bool operator!=(const ModInt &a, const ModInt &b) {return a.v != b.v;}
  friend bool operator< (const ModInt &a, const ModInt &b) {return a.v <  b.v;}
  friend bool operator<=(const ModInt &a, const ModInt &b) {return a.v <= b.v;}
  friend bool operator> (const ModInt &a, const ModInt &b) {return a.v >  b.v;}
  friend bool operator>=(const ModInt &a, const ModInt &b) {return a.v >= b.v;}
 
  ModInt &operator+=(const ModInt &a) {if ((v += a.v) >= MOD) v -= MOD; return *this;}
  ModInt &operator-=(const ModInt &a) {if ((v -= a.v) < 0) v += MOD; return *this;}
  ModInt &operator*=(const ModInt &a) {v = 1ll * v * a.v % MOD; return *this;}
  ModInt &operator/=(const ModInt &a) {return (*this) *= inverse(a);}
 
  friend ModInt pow(ModInt a, long long x) {
    ModInt res = 1;
    for (; x; x /= 2, a *= a) if (x & 1) res *= a;
    return res;
  }
  friend ModInt inverse(ModInt a) {return pow(a, MOD - 2);}
 
  ModInt operator+ () const {return ModInt( v);}
  ModInt operator- () const {return ModInt(-v);}
  ModInt operator++() const {return *this += 1;}
  ModInt operator--() const {return *this -= 1;}
 
  friend ModInt operator+(ModInt a, const ModInt &b) {return a += b;}
  friend ModInt operator-(ModInt a, const ModInt &b) {return a -= b;}
  friend ModInt operator*(ModInt a, const ModInt &b) {return a *= b;}
  friend ModInt operator/(ModInt a, const ModInt &b) {return a /= b;}
 
  friend istream &operator>>(istream &is, ModInt &v) {return is >> v.v;}
  friend ostream &operator<<(ostream &os, const ModInt &v) {return os << v.v;}
};
const int ModA	= 998244353;
const int ModC	= 1e9 + 7;
using MintA	= ModInt<ModA>;
using MintC	= ModInt<ModC>;

// Other constants
const ll INF	= 1e18;
const ll iINF	= 1e9;
const ld EPS	= 1e-9;
const ld iEPS	= 1e-6;

bool check(int l, int r, int N, vector<int> &A, int val) {
    int gr = 0, le = 0, eq = 0;
    for (int i = l; i <= r; i++) {
        if (A[i] > val) gr++;
        else if (A[i] < val) le++;
        else eq++;
    }

    bool needGreater = (gr < le);
    int target = abs(gr - le) - eq;
    // debug(target);
    
    int cur = 0;
    for (int skewGreater = 0; skewGreater <= 1; skewGreater++) {
        int cr = 0;
        for (int g = 0, l = 0, i = l-1; i >= 0; i--) {
            if (A[i] < val) {
                l++;
            } else if (A[i] == val) {
                if (skewGreater) g++;
                else l++;
            } else {
                g++;
            }
            
            if (needGreater) cr = max(cr, g-l);
            else cr = max(cr, l-g);
        }

        int cl = 0;
        for (int g = 0, l = 0, i = r+1; i < N; i++) {
            if (A[i] < val) {
                l++;
            } else if (A[i] == val) {
                if (skewGreater) g++;
                else l++;
            } else {
                g++;
            }
            
            if (needGreater) cl = max(cl, g-l);
            else cl = max(cl, l-g);
        }

        cur = max(cur, cr+cl);
    }

    return (cur >= target);
}

int sequence(int N, std::vector<int> A) {
    vector<vector<int>> occ(N+1);
    for (int i = 0; i < N; i++) occ[A[i]].push_back(i);

    // check(0, 5, 7, A, 3);
    // return -1;

    int ans = 1;
    for (int i = 1; i <= N; i++) {
        if (occ[i].empty()) continue;
        // debug(i);

        int cs = (int)occ[i].size();
        // for (int pl = 0, pr = -1; pl < cs; pl++) {
        //     while (pr + 1 < cs) {
        //         if (check(occ[i][pl], occ[i][pr+1], N, A, i)) pr++;
        //         else break;
        //     }
        //     // cout << occ[i][pl] << ' ' << occ[i][pr] << '\n';

        //     ans = max(ans, pr - pl + 1);
        // }
        for (int pl = 0; pl < cs; pl++) {
            for (int pr = pl; pr < cs; pr++) {
                if (check(occ[i][pl], occ[i][pr], N, A, i)) ans = max(ans, pr - pl + 1);
            }
        }
    }

    return ans;
}

#ifdef Zanite
int main() {
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &A[i]));
  }

  int result = sequence(N, A);
  printf("%d\n", result);
  return 0;
}
#endif

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18