結果

問題 No.2374 ASKT Subsequences
ユーザー shogo314shogo314
提出日時 2023-07-07 22:13:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 610 ms / 2,000 ms
コード長 5,588 bytes
コンパイル時間 2,446 ms
コンパイル使用メモリ 216,752 KB
最終ジャッジ日時 2025-02-15 07:35:47
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
// #include <atcoder/all>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
// using namespace atcoder;
using ll = long long;
using str = string;
using pl = pair<ll, ll>;
template <typename T>
using ml = map<ll, T>;
using mll = ml<ll>;
using sl = set<ll>;
using dbl = double;
using pd = pair<dbl, dbl>;
template <typename T>
using vec = vector<T>;
template <typename T>
using vv = vec<vec<T>>;
template <typename T1, typename T2>
using vp = vec<pair<T1, T2>>;
using vl = vec<ll>;
using vvl = vec<vl>;
using vs = vec<str>;
using vc = vec<char>;
using vpl = vec<pl>;
using vd = vec<dbl>;
using vpd = vec<pd>;
using tl3 = tuple<ll, ll, ll>;
const double INF = std::numeric_limits<double>::infinity();
#define LL(x) \
ll x; \
cin >> x;
#define STR(s) \
str s; \
cin >> s;
#define VL(a, n) \
vl a(n); \
cin >> a;
#define all(obj) (obj).begin(), (obj).end()
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define rrep(i, n) reps(i, 1, n + 1)
#define repds(i, a, n) for (ll i = (n - 1); i >= (a); i--)
#define repd(i, n) repds(i, 0, n)
#define rrepd(i, n) repds(i, 1, n + 1)
#define rep2(i, j, x, y) rep(i, x) rep(j, y)
template <typename T>
inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <typename T>
inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
os << p.first << " " << p.second;
return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != (int)v.size() ? " " : "");
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
os << vec<T>(s.begin(), s.end());
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &in : v) is >> in;
return is;
}
void print() { cout << '\n'; }
template <typename T>
void print(const T &t) {
cout << t << '\n';
}
template <typename Head, typename... Tail>
void print(const Head &head, const Tail &...tail) {
cout << head << ' ';
print(tail...);
}
void print_accurate(dbl x) {
cout << scientific << setprecision(15) << x << '\n';
}
void repr_(const ll &x) { cerr << x; }
void repr_(const int &x) { cerr << x; }
void repr_(const dbl &x) { cerr << x; }
void repr_(const str &x) { cerr << x; }
void repr_(const char &x) { cerr << x; }
void repr_(const char *x) { cerr << x; }
template <typename T1, typename T2>
void repr_(const pair<T1, T2> &p);
template <typename T1, typename T2>
void repr_(const map<T1, T2> &m);
template <typename T>
void repr_(const vec<T> &v);
template <typename T>
void repr_(const set<T> &s);
template <typename T1, typename T2>
void repr_(const pair<T1, T2> &p) {
cerr << '(';
repr_(p.first);
cerr << ", ";
repr_(p.second);
cerr << ')';
}
template <typename T>
void repr_(const vec<T> &v) {
cerr << '[';
for (int i = 0; i < (int)v.size(); i++) {
repr_(v[i]);
if (i + 1 != (int)v.size()) cerr << ", ";
}
cerr << ']';
}
template <typename T>
void repr_(const set<T> &s) {
cerr << '{';
vec<T> v = vec<T>(all(s));
for (int i = 0; i < (int)v.size(); i++) {
repr_(v[i]);
if (i + 1 != (int)v.size()) cerr << ", ";
}
cerr << '}';
}
template <typename T1, typename T2>
void repr_(const map<T1, T2> &m) {
cerr << '{';
vp<T1, T2> v = vp<T1, T2>(all(m));
for (int i = 0; i < (int)v.size(); i++) {
repr_(v[i].first);
cerr << ": ";
repr_(v[i].second);
if (i + 1 != (int)v.size()) cerr << ", ";
}
cerr << '}';
}
template <typename Head, typename... Tail>
void repr_(const Head &head, const Tail &...tail) {
repr_(head);
repr_(' ');
repr_(tail...);
}
template <typename T>
void repr(const T &t) {
repr_(t);
cerr << '\n';
}
template <typename Head, typename... Tail>
void repr(const Head &head, const Tail &...tail) {
repr_(head);
repr_(' ');
repr(tail...);
}
void solve() {
LL(N);
VL(A, N);
unordered_map<ll, vl> d;
rep(i, N) {
if (d.find(A[i]) != d.end()) {
d[A[i]].push_back(i);
} else {
d[A[i]] = vl(1, i);
}
}
ll ans = 0;
reps(k, 1, 2000) {
for (auto &i : d) {
vl a = {i.first, 0, 0, 0};
a[1] = a[0] + k + 10;
a[2] = a[1] - k;
a[3] = a[2] + k + 1;
bool f = false;
rep(j, 4) {
if (d.find(a[j]) == d.end()) f = true;
}
if (f) continue;
vpl tmp;
rep(x, 4) {
for (auto &j : d[a[x]]) {
tmp.push_back({j, x});
}
}
sort(all(tmp));
// print("tmp", tmp);
// print("a", a);
vl dp = {1, 0, 0, 0, 0};
for (auto &j : tmp) {
dp[j.second + 1] += dp[j.second];
}
// print("dp", dp);
ans += dp[4];
}
}
print(ans);
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
solve();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0