oj.uz

Submission #754966

# Submission time Handle Problem Language Result Execution time Memory
754966 2023-06-09T07:02:47 Z Zanite Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 31564 KB 
#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(needGreater);
    // debug(target);
    
    int cur = 0;
    for (int skewGreater = 0; skewGreater <= 1; skewGreater++) {
        int cl = 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) cl = max(cl, G-L);
            else cl = max(cl, L-G);
        }

        int cr = 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) cr = max(cr, G-L);
            else cr = max(cr, 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(3, 9, 10, A, 5);
    // 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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 29 ms 380 KB Output is correct
14 Correct 27 ms 340 KB Output is correct
15 Correct 44 ms 340 KB Output is correct
16 Correct 42 ms 340 KB Output is correct
17 Correct 45 ms 340 KB Output is correct
18 Correct 10 ms 420 KB Output is correct
19 Correct 25 ms 396 KB Output is correct
20 Correct 25 ms 340 KB Output is correct
21 Correct 34 ms 340 KB Output is correct
22 Correct 29 ms 340 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 2073 ms 25772 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 2080 ms 19072 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 31564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 29 ms 380 KB Output is correct
14 Correct 27 ms 340 KB Output is correct
15 Correct 44 ms 340 KB Output is correct
16 Correct 42 ms 340 KB Output is correct
17 Correct 45 ms 340 KB Output is correct
18 Correct 10 ms 420 KB Output is correct
19 Correct 25 ms 396 KB Output is correct
20 Correct 25 ms 340 KB Output is correct
21 Correct 34 ms 340 KB Output is correct
22 Correct 29 ms 340 KB Output is correct
23 Execution timed out 2079 ms 4308 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 29 ms 380 KB Output is correct
14 Correct 27 ms 340 KB Output is correct
15 Correct 44 ms 340 KB Output is correct
16 Correct 42 ms 340 KB Output is correct
17 Correct 45 ms 340 KB Output is correct
18 Correct 10 ms 420 KB Output is correct
19 Correct 25 ms 396 KB Output is correct
20 Correct 25 ms 340 KB Output is correct
21 Correct 34 ms 340 KB Output is correct
22 Correct 29 ms 340 KB Output is correct
23 Execution timed out 2073 ms 25772 KB Time limit exceeded
24 Halted 0 ms 0 KB -