Submission #1311542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311542		micodiy	A Huge Tower (CEOI10_tower)	C++20	30 / 100	391 ms	48932 KiB

tower

#ifndef CLION_DEBUG
// #pragma GCC optimize("O2")
#pragma GCC optimize("Ofast,inline,unroll-loops")
// #pragma GCC optimize("O0")
#endif

#include <bits/stdc++.h>
#include <cmath>
#include <ext/rope>

// #pragma GCC target("avx2")

// types
typedef __int128_t i128;
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef float f32;
typedef double f64;
typedef long double f80;


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

template<typename T>
using ordered_set = __gnu_pbds::tree<
    T,
    __gnu_pbds::null_type,
    std::less<>,
    __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update
>;

template<typename T>
using ordered_multiset = __gnu_pbds::tree<
    T,
    __gnu_pbds::null_type,
    std::less_equal<>,
    __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update
>;

template<typename T>
using matrix = std::vector<std::vector<T> >;

// defines
#define cto static_cast
#define int i64
#define float f64

// constants
template<typename T>
constexpr T inf = T{};

template<>
constexpr i64 inf<i64> = 4e18;
template<>
constexpr f80 inf<f80> = 1e100;
template<>
constexpr f64 inf<f64> = 1e100;
template<>
constexpr i32 inf<i32> = 1e9;

constexpr i64 prime18 = 447421542630798497;
constexpr i64 mod = 1e9 + 7;
//constexpr i64 mod = 998244353;
//constexpr i64 mod = 617980241;
constexpr f64 eps6 = 1e-6;
constexpr f64 eps10 = 1e-10;

// io
void optimize_in_out_put() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

void redirect_in_out_put(const char *input, const char *output) {
    if (input != nullptr) freopen(input, "r", stdin);
    if (output != nullptr) freopen(output, "w", stdout);
}

int read_time() {
    int a, b;
    char c;
    std::cin >> a >> c >> b;
    return a * 60 + b;
}

template<typename T>
std::pair<T, T> operator+(const std::pair<T, T> &lhs, const std::pair<T, T> &rhs) {
    return {lhs.first + rhs.first, lhs.second + rhs.second};
}

template<typename T>
std::pair<T, T> operator-(const std::pair<T, T> &lhs, const std::pair<T, T> &rhs) {
    return {lhs.first - rhs.first, lhs.second - rhs.second};
}

template<typename T>
bool operator==(const std::pair<T, T> &lhs, const std::pair<T, T> &rhs) {
    return lhs.first == rhs.first && lhs.second == rhs.second;
}

template<typename T>
T sign(T v) {
    return v > 0 ? 1 : v == 0 ? 0 : -1;
}

float gttm() {
    return (float) clock() / CLOCKS_PER_SEC;
}

struct pair_hash {
    template<typename T, typename U>
    std::size_t operator()(const std::pair<T, U> &x) const {
        return ((i128) std::hash<T>()(x.first) * (i128) std::hash<U>()(x.second)) % prime18;
    }
};

#ifdef CLION_DEBUG
#define debug_assert(c) assert(c)
#else
#define debug_assert(c)
#endif


// main code
using namespace std;

// #define TESTS_ENABLED

void solve() {
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());


    ordered_multiset<int> added;
    vector<int> dp(n);
    dp[0] = 1;
    added.insert(a[0]);
    // cout << 0 << " ";
    for (int i = 1; i < n; i++) {
        added.insert(a[i]);
        auto it = added.upper_bound(a[i] - d);
        // auto it = added.lower_bound(a[i] - d);
        auto cnt = ((int) added.size() - 1) - (int) added.order_of_key(*it);
        // cout << cnt << " ";
        dp[i] = ((i ? dp[i - 1] : 0) * (cnt + 1)) % mod;

        // cout << "!";
        // for (auto add: added) {
        //     cout << add.first << " ";
        // }
        // cout << "\n";
    }
    // cout << "\n";
    // for (int i = 0; i < dp.size(); i++)
    //     cout << dp[i] << " ";
    cout << dp.back() % mod << "\n";
}

void init() {
}

signed main() {
    init();

    optimize_in_out_put();
#ifdef CLION_DEBUG
    redirect_in_out_put("../input.txt", "../output.txt");
#else
    // ... //
#endif


    int T = 1;
#ifdef TESTS_ENABLED
    cin >> T;
#endif
    while (T--) solve();
    cout.flush(), cerr.flush();

    return 0;
}

Compilation message (stderr)

tower.cpp: In function 'void redirect_in_out_put(const char*, const char*)':
tower.cpp:80:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     if (input != nullptr) freopen(input, "r", stdin);
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~
tower.cpp:81:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     if (output != nullptr) freopen(output, "w", stdout);
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5