結果
問題 | No.8009 異なる数字の最大の範囲(勉強会用) |
ユーザー | Kiogoll |
提出日時 | 2022-02-12 22:39:28 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 95 ms / 5,000 ms |
コード長 | 5,174 bytes |
コンパイル時間 | 1,958 ms |
コンパイル使用メモリ | 184,832 KB |
実行使用メモリ | 34,400 KB |
最終ジャッジ日時 | 2024-11-20 15:08:29 |
合計ジャッジ時間 | 3,491 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
26,612 KB |
testcase_01 | AC | 10 ms
26,676 KB |
testcase_02 | AC | 11 ms
26,668 KB |
testcase_03 | AC | 11 ms
26,608 KB |
testcase_04 | AC | 10 ms
26,636 KB |
testcase_05 | AC | 10 ms
26,704 KB |
testcase_06 | AC | 11 ms
26,664 KB |
testcase_07 | AC | 10 ms
26,636 KB |
testcase_08 | AC | 12 ms
26,648 KB |
testcase_09 | AC | 11 ms
26,680 KB |
testcase_10 | AC | 11 ms
26,612 KB |
testcase_11 | AC | 12 ms
26,728 KB |
testcase_12 | AC | 11 ms
26,676 KB |
testcase_13 | AC | 10 ms
26,664 KB |
testcase_14 | AC | 11 ms
26,684 KB |
testcase_15 | AC | 57 ms
30,816 KB |
testcase_16 | AC | 51 ms
30,224 KB |
testcase_17 | AC | 53 ms
30,772 KB |
testcase_18 | AC | 95 ms
33,896 KB |
testcase_19 | AC | 66 ms
31,564 KB |
testcase_20 | AC | 34 ms
29,012 KB |
testcase_21 | AC | 21 ms
27,912 KB |
testcase_22 | AC | 41 ms
29,456 KB |
testcase_23 | AC | 25 ms
28,336 KB |
testcase_24 | AC | 84 ms
34,400 KB |
コンパイルメッセージ
main.cpp: In function 'std::string smax(std::string, std::string)': main.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type] 121 | } | ^ main.cpp: In function 'std::string smin(std::string, std::string)': main.cpp:139:1: warning: control reaches end of non-void function [-Wreturn-type] 139 | } | ^
ソースコード
#include "bits/stdc++.h" using namespace std; using ll = long long; using ull = unsigned long long; const ll _mod = 998244353; const ll _MOD = 1000000007; const ll INF = 1ll << 60; const ll inf = -(1ll << 60); const double PI = 3.141592653589793; #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() struct union_find { vector<ll> p, s; union_find(ll n) : p(n, -1), s(n, 1) {} ll root(ll x) { if (p[x] == -1) return x; else return p[x] = root(p[x]); } bool same(ll x, ll y) { return root(x) == root(y); } ll unite(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; if (s[x] < s[y]) swap(x, y); p[y] = x; s[x] += s[y]; return true; } ll size(ll x) { return s[root(x)]; } }; struct BIT { public: ll n; vector<ll> a; BIT(ll n) :n(n), a(n + 1, 0) {} void add(ll i, ll x) { i++; if (i == 0) return; for (ll k = i; k <= n; k += (k & -k)) { a[k] += x; } } ll sum(ll i, ll j) { return sum_sub(j) - sum_sub(i - 1); } ll sum_sub(ll i) { i++; ll s = 0; if (i == 0) return s; for (ll k = i; k > 0; k -= (k & -k)) { s += a[k]; } return s; } ll lower_bound(ll x) { if (x <= 0) { return 0; } else { ll i = 0; ll r = 1; while (r < n) r = r << 1; for (int len = r; len > 0; len = len >> 1) { if (i + len < n && a[i + len] < x) { x -= a[i + len]; i += len; } } return i; } } }; struct segment_tree { private: ll n; vector<ll> node; public: segment_tree(vector<ll> v) { ll sz = v.size(); n = 1; while (n < sz) n *= 2; node.resize(2 * n - 1, INF); for (ll i = 0; i < sz; i++) node[i + n - 1] = v[i]; for (ll i = n - 2; i >= 0; i--) node[i] = min(node[2 * i + 1], node[2 * i + 2]); } void update(ll x, ll val) { x += (n - 1); node[x] = val; while (x > 0) { x = (x - 1) / 2; node[x] = min(node[2 * x + 1], node[2 * x + 2]); } } ll getmin(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) { // [a, b) if (r < 0) r = n; if (r <= a || b <= l) return INF; if (a <= l && r <= b) return node[k]; ll vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2); ll vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r); return min(vl, vr); } }; string smax(string x, string y) { if (x == y) return x; if (x == "inf") return y; if (y == "inf") return x; if (x == "INF" || y == "INF") return "INF"; if (x[0] == '-' && y[0] == '-') { if (x.size() > y.size()) return y; if (x.size() < y.size()) return x; if (x.size() == y.size() && x > y) return y; if (x.size() == y.size() && x < y) return x; } if (x[0] == '-') return y; if (y[0] == '-') return x; if (x.size() > y.size()) return x; if (x.size() < y.size()) return y; if (x.size() == y.size() && x > y) return x; if (x.size() == y.size() && x < y) return y; } string smin(string x, string y) { if (x == y) return x; if (x == "INF") return y; if (y == "INF") return x; if (x == "inf" || y == "inf") return "inf"; if (x[0] == '-' && y[0] == '-') { if (x.size() > y.size()) return x; if (x.size() < y.size()) return y; if (x.size() == y.size() && x > y) return x; if (x.size() == y.size() && x < y) return y; } if (x[0] == '-') return x; if (y[0] == '-') return y; if (x.size() > y.size()) return y; if (x.size() < y.size()) return x; if (x.size() == y.size() && x > y) return y; if (x.size() == y.size() && x < y) return x; } vector<pair<ll, ll>> prime_factorization(ll x) { vector<pair<ll, ll>> ans(0); for (ll p = 2; p * p <= x; ++p) { if (!(x % p)) { ll e = 0; while (!(x % p)) { x %= p; ++e; } ans.push_back({ p,e }); } } if (x != 1) ans.push_back({ x,1 }); return ans; } ll phi(ll x) { const auto& pf = prime_factorization(x); ll ans = x; for (pair<ll, ll> p : pf) { ans *= (p.first - 1); ans *= p.first; } return ans; } ll modinv(ll x, ll MOD) { ll y = MOD, u = 1, v = 0; while (y) { ll t = x / y; x -= t * y; swap(x, y); u -= t * v; swap(u, v); } u %= MOD; if (u < 0) u += MOD; return u; } ll modpow(ll a, ll n, ll MOD) { ll ans = 1; while (n > 0) { if (n & 1) ans = ans * a % MOD; a = a * a % MOD; n >>= 1; } return ans; } vector<ll> _f(1000001), _finv(1000001), _inv(1000001); void Cinit(ll MOD) { _f[0] = 1; _f[1] = 1; _finv[0] = 1; _finv[1] = 1; _inv[1] = 1; for (ll i = 2; i < 1000001; ++i) { _f[i] = _f[i - 1] * i % MOD; _inv[i] = MOD - _inv[MOD % i] * (MOD / i) % MOD; _finv[i] = _finv[i - 1] * _inv[i] % MOD; } } ll modnCr(ll n, ll r, ll MOD) { if (n < r) return 0; if (n < 0 || r < 0) return 0; return _f[n] * (_finv[r] * _finv[n - r] % MOD) % MOD; } ll modnHr(ll n, ll r, ll MOD) { return modnCr(n + r - 1, r, MOD); } int main() { ll N, last = 0, ans = -1; cin >> N; vector<ll> A(N), a(N); map<ll, ll> m; for (ll i = 0; i < N; ++i) { cin >> A[i]; a[i] = max(last, m[A[i]]); m[A[i]] = i + 1; last = a[i]; ans = max(ans, i - a[i] + 1); } cout << ans << "\n"; }