Submission #61551267

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef LOCAL
#pragma GCC optimize("Ofast", "unroll-loops")
#endif
#include <bits/stdc++.h>
#include <unistd.h>
#define FASTIO
namespace mitsuha::io {
#define READ_INTEGRAL(type_t) void rd(type_t &x) { rd_integer(x); }
#define READ_FLOATING(type_t) void rd(type_t &x) { rd_real(x); }
#define WRITE_INTEGRAL(type_t) void wt(type_t x) { wt_integer(x); }
#define WRITE_FLOATING(type_t) void wt(type_t x) { wt_real(x); }
static constexpr uint32_t SZ = 1 << 17;
char input_buffer[SZ];
char output_buffer[SZ];
char out[100];
uint32_t pil = 0, pir = 0, por = 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ifndef LOCAL
#pragma GCC optimize("Ofast", "unroll-loops")
#endif

#include <bits/stdc++.h>

#include <unistd.h>

#define FASTIO
namespace mitsuha::io {
#define READ_INTEGRAL(type_t) void rd(type_t &x) { rd_integer(x); }
#define READ_FLOATING(type_t) void rd(type_t &x) { rd_real(x); }
#define WRITE_INTEGRAL(type_t) void wt(type_t x) { wt_integer(x); }
#define WRITE_FLOATING(type_t) void wt(type_t x) { wt_real(x); }

static constexpr uint32_t SZ = 1 << 17;
char input_buffer[SZ];
char output_buffer[SZ];
char out[100];
uint32_t pil = 0, pir = 0, por = 0;

struct Pre {
    char num[10000][4];
    constexpr Pre() : num() {
        for (int i = 0; i < 10000; i++) {
            for (int j = 3, n = i; j >= 0; j--, n /= 10) {
                num[i][j] = n % 10 | '0';
            }
        }
    }
} constexpr pre;

inline void load() {
    memcpy(input_buffer, input_buffer + pil, pir - pil);
    pir = pir - pil + fread(input_buffer + pir - pil, 1, SZ - pir + pil, stdin);
    pil = 0;
    if (pir < SZ) input_buffer[pir++] = '\n';
}
inline void flush() {
    fwrite(output_buffer, 1, por, stdout);
    por = 0;
}
void rd(char &c) { 
    do { 
        if (pil >= pir) load(); 
        c = input_buffer[pil++]; 
    } while (isspace(c));
}
void rd(std::string &x) {
    x.clear();
    char c;
    do { 
        if (pil >= pir) load(); 
        c = input_buffer[pil++]; 
    } while (isspace(c));
    do {
        x += c;
        if (pil == pir) load();
        c = input_buffer[pil++];
    } while (!isspace(c));
}
template<typename T>
void rd_real(T &x) {
    std::string s;
    rd(s);
    x = stod(s);
}
template<typename T>
void rd_integer(T &x) {
    if (pil + 100 > pir) load();
    char c;
    do c = input_buffer[pil++]; while (c < '-');
    bool minus = 0;
    if constexpr (std::is_signed<T>::value or std::is_same_v <T, __int128 >) {
        if (c == '-') {
            minus = 1;
            c = input_buffer[pil++];
        }
    }
    x = 0;
    while ('0' <= c) { x = x * 10 + (c & 15), c = input_buffer[pil++]; }
    if constexpr (std::is_signed<T>::value or std::is_same_v < T, __int128 >) {
        if (minus) x = -x;
    }
}

READ_INTEGRAL(int) 
READ_INTEGRAL(long int)
READ_INTEGRAL(long long)
READ_INTEGRAL(__int128)
READ_INTEGRAL(unsigned int)
READ_INTEGRAL(unsigned long long)
READ_INTEGRAL(unsigned __int128)
READ_FLOATING(double)
READ_FLOATING(long double)
READ_FLOATING(__float128)

template<class T, class U> void rd(std::pair <T, U> &p) {
    rd(p.first);
    rd(p.second);
}
template<size_t N = 0, typename T> void rd_tuple(T &t) {
    if constexpr (N < std::tuple_size<T>::value) {
        auto &x = std::get<N>(t);
        rd(x);
        rd_tuple<N + 1>(t);
    }
}
template<class... T> void rd(std::tuple<T...> &tpl) {
    rd_tuple(tpl);
}
template<size_t N = 0, typename T> void rd(std::array <T, N> &x) {
    for (auto &d: x) rd(d);
}
template<class T> void rd(std::vector <T> &x) {
    for (auto &d: x) rd(d);
}

void read() {}
template<class Head, class... Args>
void read(Head &h, Args &... t) {
    rd(h);
    read(t...);
}

void wt(const char c) {
    if (por == SZ) flush();
    output_buffer[por++] = c;
}
void wt(const std::string &s) {
    for (char c: s) wt(c);
}
void wt(const char *s) {
    size_t len = strlen(s);
    for (size_t i = 0; i < len; i++) wt(s[i]);
}
template<typename T>
void wt_integer(T x) {
    if (por > SZ - 100) flush();
    if (x < 0) { output_buffer[por++] = '-', x = -x; }
    int outi;
    for (outi = 96; x >= 10000; outi -= 4, x /= 10000) {
        memcpy(out + outi, pre.num[x % 10000], 4);
    }
    if (x >= 1000) {
        memcpy(output_buffer + por, pre.num[x], 4);
        por += 4;
    }
    else if (x >= 100) {
        memcpy(output_buffer + por, pre.num[x] + 1, 3);
        por += 3;
    }
    else if (x >= 10) {
        int q = (x * 103) >> 10;
        output_buffer[por] = q | '0';
        output_buffer[por + 1] = (x - q * 10) | '0';
        por += 2;
    }
    else output_buffer[por++] = x | '0';
    memcpy(output_buffer + por, out + outi + 4, 96 - outi);
    por += 96 - outi;
}
template<typename T>
void wt_real(T x) {
    std::ostringstream oss;
    oss << std::fixed << std::setprecision(15) << double(x);
    std::string s = oss.str();
    wt(s);
}

WRITE_INTEGRAL(int)
WRITE_INTEGRAL(long int)
WRITE_INTEGRAL(long long)
WRITE_INTEGRAL(__int128)
WRITE_INTEGRAL(unsigned int)
WRITE_INTEGRAL(unsigned long long)
WRITE_INTEGRAL(unsigned __int128)
WRITE_FLOATING(double)
WRITE_FLOATING(long double)
WRITE_FLOATING(__float128)

template<class T, class U>
void wt(const std::pair <T, U> val) {
    wt(val.first);
    wt(' ');
    wt(val.second);
}
template<size_t N = 0, typename T>
void wt_tuple(const T t) {
    if constexpr (N < std::tuple_size<T>::value) {
        if constexpr (N > 0) { wt(' '); }
        const auto x = std::get<N>(t);
        wt(x);
        wt_tuple<N + 1>(t);
    }
}
template<class... T> void wt(std::tuple<T...> tpl) {
    wt_tuple(tpl);
}
template<class T, size_t S> void wt(const std::array <T, S> val) {
    for (size_t i = 0, n = val.size(); i < n; i++) {
        if (i) wt(' ');
        wt(val[i]);
    }
}
template<class T> void wt(const std::vector<T> val) {
    for (size_t i = 0, n = val.size(); i < n; i++) {
        if (i) wt(' ');
        wt(val[i]);
    }
}

void print() { wt('\n'); }
template<class Head, class... Args>
void print(Head &&head, Args &&... args) {
    wt(head);
    if (sizeof...(Args)) wt(' ');
    print(std::forward<Args>(args)...);
}

void __attribute__((destructor)) _d() {
    flush(); 
}
} // namespace mitsuha::io

namespace mitsuha {
    using io::read; using io::print; using io::flush;
}

namespace mitsuha {
template <class T> bool chmin(T& x, const T& y) { 
    return y >= x ? false : (x = y, true); 
}
template <class T> bool chmax(T& x, const T& y) { 
    return y <= x ? false : (x = y, true); 
}
template <class T> constexpr T fld(const T x, const T y) { 
    T q = x / y, r = x % y; return q - ((x ^ y) < 0 and (r != 0)); 
}
template <class T> constexpr T cld(const T x, const T y) { 
    T q = x / y, r = x % y; return q + ((x ^ y) > 0 and (r != 0)); 
}
template <class T> constexpr T rem(const T x, const T y) { 
    return x - y * fld(x, y); 
}
template <class Iterable> void settify(Iterable& a) { 
    std::sort(a.begin(), a.end()), a.erase(std::unique(a.begin(), a.end()), a.end()); 
}
template <typename T, typename... Vectors>
void concat(std::vector<T> &first, const Vectors &... others) {
    std::vector<T> &res = first;
    (res.insert(res.end(), others.begin(), others.end()), ...);
}
template<typename T>
std::map<T, int> Counter(std::vector<T> &a){
    std::map<T, int> cnt;
    for (auto &x: a) ++cnt[x];
    return cnt;
}
template <typename T>
std::vector<int> argsort(const std::vector<T> &A) {
    std::vector<int> ids(A.size());
    std::iota(ids.begin(), ids.end(), 0);
    std::sort(ids.begin(), ids.end(), [&](int i, int j) { 
        return (A[i] == A[j] ? i < j : A[i] < A[j]); 
    });
    return ids;
}
template <typename T>
std::vector<T> rearrange(const std::vector<T> &A, const std::vector<int> &I) {
    std::vector<T> B(I.size());
    for(int i = 0; i < I.size(); ++i) B[i] = A[I[i]];
    return B;
}
template <size_t D> struct Dim : std::array<int, D> {
    template <typename ...Ints> Dim(const Ints& ...ns) : 
        std::array<int, D>::array{ static_cast<int>(ns)... } {}
};
template <typename ...Ints> Dim(const Ints& ...) -> Dim<sizeof...(Ints)>;
template <class T, size_t D, size_t I = 0>
auto ndvec(const Dim<D> &ns, const T& value = {}) {
    if constexpr (I + 1 < D) {
        return std::vector(ns[I], ndvec<T, D, I + 1>(ns, value));
    } else {
        return std::vector<T>(ns[I], value);
    }
}
}

namespace mitsuha {
using str = std::string;
using int128 = __int128;
using uint128 = unsigned __int128;
template <class T> using min_priority_queue 
                            = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T> using max_priority_queue 
                            = std::priority_queue<T, std::vector<T>, std::less<T>>;
}
namespace mitsuha { 
    const std::vector<std::string> Yes = {"No", "Yes"};
    const std::vector<std::string> YES = {"NO", "YES"};
}
 
#ifndef __COUNTER__
#define __COUNTER__ __LINE__
#endif

#define TL (long long)
#define Sq(x) ((x) * (x))

#define OVERLOAD5(a, b, c, d, e, ...) e
#define REP1_0(b, c) REP1_1(b, c)
#define REP1_1(b, c) for (long long REP_COUNTER_##c = 0; REP_COUNTER_##c < TL(b); ++REP_COUNTER_##c)
#define REP1(b) REP1_0(b, __COUNTER__)
#define REP2(i, b) for (long long i = 0; i < TL(b); ++i)
#define REP3(i, a, b) for (long long i = TL(a); i < TL(b); ++i)
#define REP4(i, a, b, c) for (long long i = TL(a); i < TL(b); i += TL(c))
#define For(...) OVERLOAD5(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define RREP2(i, a) for (long long i = TL(a)-1; i >= 0; --i)
#define RREP3(i, a, b) for (long long i = TL(b)-1; i >= TL(a); --i)
#define RREP4(i, a, b, c) for (long long i = TL(b)-1; i >= TL(a); i -= TL(c))
#define Frr(...) OVERLOAD5(__VA_ARGS__, RREP4, RREP3, RREP2)(__VA_ARGS__)

#define Int(...) int __VA_ARGS__; read(__VA_ARGS__)
#define Ll(...) long long __VA_ARGS__; read(__VA_ARGS__)
#define Dbl(...) double __VA_ARGS__; read(__VA_ARGS__)
#define Chr(...) char __VA_ARGS__; read(__VA_ARGS__)
#define Str(...) string __VA_ARGS__; read(__VA_ARGS__)
#define Vt(type, name, size) vector<type> name(size); read(name)
#define Vvt(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); read(name)
#define die_int(...) do { print(__VA_ARGS__); return; } while (false)
#define die_ext(...) do { print(__VA_ARGS__); return 0; } while (false)

#define All(iterable) std::begin(iterable), std::end(iterable)
#define len(iterable) TL iterable.size()
#define elif else if

#define KBIT(a, k) ((a >> k) & 1)

using namespace mitsuha;
using namespace std;

#ifdef LOCAL
#define  debug_path "library/debug/pprint.hpp"
#include debug_path
#define Assert(x) assert(x)
#else
#define debug(...) void(0)
#define debug2(...) void(0)
#define debugbin(...) void(0)
#define Assert(x) void(0)
#endif
 
constexpr int iinf = std::numeric_limits<int>::max() / 2;
constexpr long long linf = std::numeric_limits<long long>::max() / 2;

namespace mitsuha{
template <typename T> int count_leq(const vector<T> &v, const T &key) { return upper_bound(v.begin(), v.end(), key) - v.begin();  }
template <typename T> int count_lt(const vector<T> &v, const T &key) { return lower_bound(v.begin(), v.end(), key) - v.begin();  }
template <typename T> int count_geq(const vector<T> &v, const T &key) { return v.size() - count_lt(v, key); }
template <typename T> int count_gt(const vector<T> &v, const T &key) { return v.size() - count_leq(v, key); }

template <typename Container, typename Key>
auto min_geq(const Container &container, const Key &key) -> decltype(make_optional(*container.lower_bound(key))) {
    if (auto it = container.lower_bound(key); it == container.end()) return nullopt;
    else return make_optional(*it);
}
template <typename Container, typename Key>
auto min_gt(const Container &container, const Key &key) -> decltype(make_optional(*container.upper_bound(key))) {
    if (auto it = container.upper_bound(key); it == container.end()) return nullopt;
    else return make_optional(*it);
}
template <typename Container, typename Key>
auto max_leq(const Container &container, const Key &key) -> decltype(make_optional(*container.upper_bound(key))) {
    if (auto it = container.upper_bound(key); it == container.begin()) return nullopt;
    else return make_optional(*--it);
}
template <typename Container, typename Key>
auto max_lt(const Container &container, const Key &key) -> decltype(make_optional(*container.lower_bound(key))) {
    if (auto it = container.lower_bound(key); it == container.begin()) return nullopt;
    else return make_optional(*--it);
}
template <typename T>
optional<T> min_geq(const vector<T> &v, const T &key) {
    auto it = lower_bound(v.begin(), v.end(), key);
    return it == v.end() ? nullopt : make_optional(*it);
}
template <typename T>
optional<T> min_gt(const vector<T> &v, const T &key) {
    auto it = upper_bound(v.begin(), v.end(), key);
    return it == v.end() ? nullopt : make_optional(*it);
}
template <typename T>
optional<T> max_leq(const vector<T> &v, const T &key) {
    auto it = upper_bound(v.begin(), v.end(), key);
    return it == v.begin() ? nullopt : make_optional(*--it);
}
template <typename T>
optional<T> max_lt(const vector<T> &v, const T &key) {
    auto it = lower_bound(v.begin(), v.end(), key);
    return it == v.begin() ? nullopt : make_optional(*--it);
}
} // namespace mitsuha

int main(){
    
    Int(n);
    Vt(int, a, n);

    long long ret = 0;
    For(x, n) ret += count_leq(a, a[x] / 2);
    print(ret);
    return 0;
}

Submission Info

Judge Result