oj.uz

Submission #839673

# Submission time Handle Problem Language Result Execution time Memory
839673 2023-08-30T11:59:32 Z Peter_Peter A Huge Tower (CEOI10_tower) C++17
100 / 100
 99 ms 20912 KB 
#include <bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define mod 1000000009
#define inf 1e18
#define endl "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, init, n) for (int i = init; i < (int)n; i++)
#define rev(i, n, init) for (int i = (int)n; i >= init; i--)
#define V vector<int>
#define VV vector<V>
#define Vll vector<ll>
#define VVll vector<Vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define Vpii vector<pii>
// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // find_by_order, order_of_key
#ifndef anurag203
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}

//vector<bool> isprime;
vector<bool> SieveOfEratosthenes(ll n){
vector<bool> prime(n + 1, 1); for (ll p = 2; p * p <= n; p++)
if (prime[p] == true) for (ll i = p * p; i <= n; i += p)
prime[i] = false; return prime;}

ll powe(ll x,ll y, ll p=mod){
ll res = 1; x = x % p;
while (y > 0){ if (y & 1) res = (res * x) % p;
y = y >> 1; x = (x * x) % p;} return res;}

ll inverse_modulo(ll a, ll p = mod)
{return powe(a, p - 2, p);}
////factorial vector
// Vll fact(200000, 1);
// void fill_fact(ll p = mod){rep(i, 1, 200000){fact[i] = (fact[i - 1] * i) % p;}}
////nCr fermat
// ll C(ll n,ll r,ll p=mod)
// {return ((fact[n]*inverse_modulo(fact[n-r]))%mod*inverse_modulo(fact[r]))%mod;}

template <class T, class vv> void _print(pair <T, vv> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class vv> void _print(map <T, vv> v);
template <class T> void _print(multiset <T> v);
template <class T, class vv> void _print(pair <T, vv> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class vv> void _print(map <T, vv> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
/*----------------------------------------------------------------------------------------------------------------------------------------------------*/

void solve()
{
    ll n, d; cin >> n >> d;
    Vll a(n); rep(i, 0, n) cin >> a[i];
    sort(all(a)); Vll b(n);
    int l = 0, r = 0;
    while (l < n)
    {
        while (r+1 < n && a[l] + d >= a[r+1])
        {
            r++;
            b[r] = r - l;
        }
        l++;
    }
    Vll ans(n); ans[0] = 1;
    rep(i,1,n)
    {
        ans[i] = ans[i - 1] * (b[i] + 1);
        ans[i] %= mod;
    }
    cout << ans[n - 1] << endl;
}
int main() {
#ifndef Anurag203
    freopen("Error.txt", "w", stderr);
#endif
    fastio();
    // freopen("output.in", "r", stdin);
    // freopen("output.out", "w", stdout);

    int tt = 1;
    // cin>>tt;
    while (tt--)
    {
        solve();
    }       
    return 0;
}

Compilation message

tower.cpp: In function 'std::vector<bool> SieveOfEratosthenes(long long int)':
tower.cpp:43:23: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 | if (prime[p] == true) for (ll i = p * p; i <= n; i += p)
      |                       ^~~
tower.cpp:44:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   44 | prime[i] = false; return prime;}
      |                   ^~~~~~
tower.cpp: In function 'int main()':
tower.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     freopen("Error.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2048 KB Output is correct
2 Correct 8 ms 2004 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8564 KB Output is correct
2 Correct 38 ms 8536 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 20912 KB Output is correct
2 Correct 99 ms 20368 KB Output is correct