Submission #1043197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043197		mohitdmak	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	56 ms	12372 KiB

triusis

/////////////////////////////////////////////// EPILOGUE ///////////////////////////////////////////////
// Author: @mohitdmak 
// NOTE: code inside this fxn at end of template or after importing it
// void start(){ }
/////////////////////////////////////////////// END ///////////////////////////////////////////////

/////////////////////////////////////////////// GCC AND LIBS OPTIMIZATIONS ///////////////////////////////////////////////
#pragma GCC optimize("Ofast")
// #pragma GCC optimize("O0") // for something related to double precision optimization? (checkout)
// // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") // below removed "avx2" as SPOJ gives runtime error due to "SIGILL" for some reason
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,fma")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h" // going for precompiling headers for stl lib collection (#include <bits/stdc++.h>) through make job
using namespace std;
#ifndef ONLINE_JUDGE
    #include <sys/resource.h>
#endif
/////////////////////////////////////////////// END ///////////////////////////////////////////////

/////////////////////////////////////////////// DEBUGGING FUNCTIONS ///////////////////////////////////////////////
// COUTing pairs 
template <typename S, typename V>
ostream& operator<<(ostream& os, const pair<S, V>& ppair) {
    os << "P:{" << ppair.first << "," << ppair.second << "}";
    return os;
}
// COUTing sets (only 1Ds at the moment)
// template <typename S, class Iterator>
template <typename S, typename V>
ostream& operator<<(ostream& os, const set<S, V>& sset) {
    os << "Set:[";
    for (auto element : sset) { os << element << ","; }
    os << "]";
    return os;
}
// COUTing multisets (only 1Ds at the moment)
// template <typename T, typename S, typename V>
template <typename S, typename V>
ostream& operator<<(ostream& os, const multiset<S, V>& mset) {
    os << "MSet:[";
    for (auto element : mset) { os << element << ","; }
    os << "]";
    return os;
}
// COUTing vectors (only 1Ds at the moment) 
template <typename S>
ostream& operator<<(ostream& os, const vector<S>& vvector) {
    os << "V:[";
    for (auto element : vvector) { os << element << ","; }
    os << "]";
    return os;
}
// COUTing deques 
template <typename S>
ostream& operator<<(ostream& os, const deque<S>& ddeque) {
    os << "Dq:[";
    for (auto element : ddeque) { os << element << ","; }
    os << "]";
    return os;
}
// COUTing maps (only 1Ds at the moment)
template <typename S, typename V>
ostream& operator<<(ostream& os, const map<S, V>& mmap) {
    os << "M:[";
    for (auto element : mmap) { os << element.first << ":" << element.second << ","; }
    os << "]";
    return os;
}
// COUTing unordered maps (only 1Ds at the moment)
template <typename S, typename V>
ostream& operator<<(ostream& os, const unordered_map<S, V>& mmap) {
    os << "uM:[";
    for (auto element : mmap) { os << element.first << ":" << element.second << ","; }
    os << "]";
    return os;
}
// COUTing queues
template <typename T>
ostream& operator<<(ostream& os, queue<T> mq) {
    os << "Q:[";
    while (mq.size()){
        T element = mq.front(); mq.pop();
        os << element << ",";
    }
    os << "]";
    return os;
}
// COUTing stacks
template <typename T>
ostream& operator<<(ostream& os, stack<T> mq) {
    os << "S:[";
    while (mq.size()){
        T element = mq.top(); mq.pop();
        os << element << ",";
    }
    os << "]";
    return os;
}
// COUTing priority_queue
// template <typename T, typename S, typename V>
template <typename T, typename S, typename V>
ostream& operator<<(ostream& os, const priority_queue<T, S, V>& mpq) {
    priority_queue<T, S, V> copyPQ(mpq);
    os << "PQ:[";
    while (copyPQ.size()) { os << copyPQ.top() << ","; copyPQ.pop(); }
    os << "]";
    return os;
}
/* debugging error variables and values */
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); cerr << "\nDEBUG: "; err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << "; ";
	err(++it, args...);
}
vector<string> X_splitStr(string s, vector<string> delims){
    string curr = s;
    int curr_pos = 0;
    vector<string> tokenized;
    while(curr.size()){
        int delim_size = 0;
        for (string delim: delims){
            int curr_size = (int)curr.size();
            curr = curr.substr(0, curr.find(delim));
            if ((int)curr.size() != curr_size) delim_size = delim.size();
        }
        curr_pos += (int)curr.size() + delim_size;
        if (curr.size()) tokenized.push_back(curr);
        curr = s.substr(curr_pos);
    }
    return tokenized;
}
/////////////////////////////////////////////// END ///////////////////////////////////////////////

/////////////////////////////////////////////// SHORTHANDS / DEFINITIONS ///////////////////////////////////////////////
#define _n_ << "\n"  // newline
#define __ << " " << // space
const int BS = 21; // no of bits to print in X_BS
const int MOD = 1e9 + 7;
typedef long long ll;
vector<ll> FACTORIALS;
/////////////////////////////////////////////// END ///////////////////////////////////////////////

/////////////////////////////////////////////// UTILITY FUNCTIONS ///////////////////////////////////////////////
// Matrix ops like power (bin exponentiation), etc <==> (Template is just to support int / long long)
template<class T> struct X_Mat{
    vector<vector<T>> mat; int r, c, mod; // mod is used during mul ops
    X_Mat(): r(0), c(0) {} // default constructor (don't initialize vector 'o vector)
    X_Mat(int r_, int c_, int mod_ = 0, int val_ = 0): r(r_), c(c_), mod(mod_) { mat = vector<vector<T>>(r_, vector<T>(c, val_)); }
    X_Mat operator*(const X_Mat &mat2){ // mul op -> O(N^3) where |mat| ~ N x N
        assert(c == mat2.r); // m1 x m2 -> can only cross if of form [axb]X[bxc]
        X_Mat res(r, mat2.c, mod); // response matrix (carry forth mod info, initialize with 0s)
        for (int i = 0; i < r; i++) for (int j = 0; j < mat2.c; j++) for (int k = 0; k < c; k++){ // matrix mul
            if (!mod) res.mat[i][j] += mat[i][k] * mat2.mat[k][j];
            else res.mat[i][j] = (res.mat[i][j] + (1ll * mat[i][k] * mat2.mat[k][j] % mod)) % mod;
        }
        return res;
    }
    X_Mat operator*=(const X_Mat &mat2){ return *this = (*this) * mat2; } // simply assign res of mul op
    // O(N^3.log(p)) -> friend function to use externally, using bin exponentiation on matrices
    friend X_Mat X_MatPower(X_Mat m, ll p){ 
        assert(m.r == m.c); // only square matrices can be raised to powers
        X_Mat res(m.r, m.c, m.mod); // response matrix (in bin exponentiation we gotta ensure identity matrix to mul with mat)
        for (int i = 0; i < m.r; i++) res.mat[i][i] = 1;
        for (; p; p >>= 1){ // bin exponentiation
            if (p & 1) res *= m;
            m *= m;
        }
        return res;
    }
};
// Double-Ended Priority Queue
class X_DoublePQ{
public:
    multiset<int> pq;
    // O(1) returns size of priority queue
    int size() { return (int)pq.size(); }
    // O(logn) inserts into priority queue
    void insert(int x) { pq.insert(x); }
    // O(1) gets min el
    int min() { return *pq.begin(); }
    // O(1) gets max el
    int max() { return *pq.rbegin(); }
    // O(logn) deletes min el
    void deleteMin() { 
        if (!pq.size()) return;
        pq.erase(pq.begin());
    }
    // O(logn) deletes max el
    void deleteMax() { 
        if (!pq.size()) return;
        auto itr = pq.end(); itr--;
        pq.erase(itr);
    }
};
// DSU
class X_DSU{
public: 
    vector<ll> id;
    vector<ll> size;
    void make_set(ll n){
        id = vector<ll> (n);
        size = vector<ll> (n, 1);
        for (ll i = 0; i < n; i++) id[i] = i;
    }
    void clear_set(){
        for (ll i = 0; i < (ll)id.size(); i++) { id[i] = i; size[i] = 1; }
    }
    ll find_set(ll v){
        if (v == id[v]) return v;
        return id[v] = find_set(id[v]);
    }
    ll total_set(){
        ll total = 0;
        for (ll i = 0; i < (ll)id.size(); i++) total += (i == id[i]) ? 1 : 0;
        return total;
    }
    void union_set(ll u, ll v){
        ll uID = find_set(u), vID = find_set(v);
        if (uID != vID){
            if (size[uID] > size[vID]){
                id[vID] = uID;
                size[uID] += size[vID];
            } else {
                id[uID] = vID;
                size[vID] += size[uID];
            }
        }
    }
};
// Get bitset print of input
bitset<BS> X_bs(ll ip){ return bitset<BS>(ip); }
bitset<BS> X_bs(int ip){ return bitset<BS>(ip); }
// Returns random in [a,b]
int X_rand(int a, int b) { return a + rand() % (b - a + 1); }
// Euclid's gcd algorithm
// $$ TIME: O(log(min(a, b)))
ll X_gcd (ll a, ll b){
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
// Euclid's extended algorithm, find x,y s.t ax + by = gcd(a,b)
// $$ TIME: O(log(min(a, b)))
ll X_gcd_extended(ll a, ll b, ll& x, ll& y){
    x = 1, y = 0;
    ll x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        ll q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}
// Computes the total no of solutions (x,y) for `ax + by = c`, with x1<=x<=x2 and y1<=y<=y2, returns -1 if ~infinite sols
// $$ TIME: O(log(min(a,b)))
ll X_diophantine_total_sols(ll a, ll b, ll c, pair<ll, ll> xRange = {0, LLONG_MAX}, pair<ll, ll> yRange = {0, LLONG_MAX}){
    // checking for any infinity type bound
    bool infInvolved = (xRange.second == LLONG_MAX || yRange.second == LLONG_MAX || xRange.first == LLONG_MIN || yRange.first == LLONG_MIN);
    // PRUNE: Edge Cases
    if (!a && !b && c) return 0;
    else if (!a && !b && !c) return ((infInvolved) ? -1 : (xRange.second - xRange.first + 1) * (yRange.second - yRange.first + 1));
    else if (!a || !b){
        if (!a){
            if (!(c % b) && yRange.first <= (c / b) && (c / b) <= yRange.second) return ((!infInvolved) ? xRange.second - xRange.first + 1 : -1);
            else return 0;
        } else {
            if (!(c % a) && xRange.first <= (c / a) && (c / a) <= xRange.second) return ((!infInvolved) ? yRange.second - yRange.first + 1 : -1);
            else return 0;
        }
    }
    // Getting a single solution
    ll x, y, g;
    g = X_gcd_extended((ll)a, (ll)b, x, y);
    if (c % g) return 0;
    ll x0 = x * (c / g), y0 = y * (c / g);
    double ag = a / g, bg = b / g;
    // Getting range of k for x,y and combined range kZ
    pair<ll, ll> kX, kY, kZ;
    if (kX.first == LLONG_MIN) kX.first = LLONG_MIN; 
    else kX.first = (x0 >= xRange.first) ? -floor((double)(x0 - xRange.first) / abs(bg)) : ceil((double)(xRange.first - x0) / abs(bg));
    if (kY.first == LLONG_MIN) kY.first = LLONG_MIN;
    else kY.first = (y0 >= yRange.first) ? -floor((double)(y0 - yRange.first) / abs(ag)) : ceil((double)(yRange.first - y0) / abs(ag));
    if (xRange.second == LLONG_MAX) kX.second = LLONG_MAX;
    else kX.second = (x0 >= xRange.second) ? -ceil((double)(x0 - xRange.second) / abs(bg)) : floor((double)(xRange.second - x0) / abs(bg));
    if (yRange.second == LLONG_MAX) kY.second = LLONG_MAX;
    else kY.second = (y0 >= yRange.second) ? -ceil((double)(y0 - yRange.second) / abs(ag)) : floor((double)(yRange.second - y0) / abs(ag));
    if (bg < 0) kX = {-kX.second, -kX.first};
    if (ag < 0) kY = {-kY.second, -kY.first};
    kZ = {-kY.second, -kY.first};
    // Prune and return
    if ((kY.first > kY.second) || (kX.first > kX.second)) return 0;
    kZ = {max(kZ.first, kX.first), min(kZ.second, kX.second)};
    return ((kZ.first <= kZ.second) ? kZ.second - kZ.first + 1 : 0);
}
// Computes and returns all primes upto n as a bool array; 
// possible optimizations - see for only odd nos (memory & time halved, done if `ignoreEven`) / see segmented sieve
// $$ TIME: O(n log(log n)); MEMORY [IMP]: O(n)
vector<bool> X_sieve(ll n, bool ignoreEven = false){
    vector<bool> is_prime(n+1, true);
    is_prime[2] = true;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2 + (int)ignoreEven; i * i <= n; i += 1 + (int)ignoreEven) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i * (1 + (int)ignoreEven)) is_prime[j] = false;
        }
    }
    return is_prime;
}
// Computes only the COUNT of primes upto n; Better than X_sieve on memory - O(sqrt(n)); if `store` is true, primes are stored in `allPrimes`
// $$ TIME: O(n log(log sqrt(n))); MEMORY [IMP]: O(sqrt(n))
ll X_sieve_segmented_count(ll n, vector<ll> &allPrimes, bool store = false) {
    const ll S = 10000; // block/segment size (generally 1e4 - 1e5)
    vector<ll> primes;
    ll nsqrt = sqrt(n);
    vector<char> is_prime(nsqrt + 2, true);
    for (ll i = 2; i <= nsqrt; i++) { // store primes till sqrt(n)
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = i * i; j <= nsqrt; j += i) {
                is_prime[j] = false;
            }
        }
    }
    ll result = 0; // total count of primes
    vector<char> block(S);
    for (ll k = 0; k * S <= n; k++) { // mark primes for each block
        fill(block.begin(), block.end(), true);
        ll start = k * S;
        for (ll p : primes) {
            ll start_idx = (start + p - 1) / p;
            ll j = max(start_idx, p) * p - start;
            for (; j < S; j += p)
                block[j] = false;
        }
        if (k == 0) block[0] = block[1] = false;
        for (ll i = 0; i < S && start + i <= n; i++) {
            if (block[i]){
                result++;
                if (store) allPrimes.push_back(start + i); // actual prime no is start+i, store if told
            }
        }
    }
    return result;
}
// Computes and stores bool of array of primes in range [L, R]; Uses segmented Seive
// $$ TIME: O(n log(log sqrt(n))); MEMORY [IMP]: O(sqrt(n)) [n = R - L]
vector<bool> X_sieve_segmented_all(ll L, ll R) {
    // generate all primes up to sqrt(R)
    ll lim = sqrt(R);
    vector<char> mark(lim + 1, false);
    vector<ll> primes;
    for (ll i = 2; i <= lim; ++i) {
        if (!mark[i]) {
            primes.emplace_back(i);
            for (ll j = i * i; j <= lim; j += i){
                mark[j] = true;
            }
        }
    }
    vector<bool> isPrime(R - L + 1, true);
    for (ll i : primes){
        for (ll j = max(i * i, (L + i - 1) / i * i); j <= R; j += i){
            isPrime[j - L] = false;
        }
    }
    if (L == 1) isPrime[0] = false;
    return isPrime;
}
// get prime factors, returns vector of pairs of ll, where first == prime factor, second == it's power
//
// $$ TIME: O(sqrt(N))
vector<pair<ll, ll>> prime_factors_sqrt(ll N){
    ll prime = 2, n = N;
    vector<pair<ll, ll>> res(0);
    while (prime * prime <= n){
        if (N % prime == 0) {
            ll count = 0;
            while (N % prime == 0) { N /= prime; count++; }
            res.push_back({prime, count});
        }
        prime++;
    }
    return res;
}
// get prime factors, returns vector of pairs of ll, where first == prime factor, second == it's power
//
// $$ TIME: O(log(N)) for composite N; O(N) for prime N
vector<pair<ll, ll>> prime_factors_sieve(ll N){
    ll prime = 2;
    vector<pair<ll, ll>> res(0);
    while (N > 1){
        if (N % prime == 0) {
            ll count = 0;
            while (N % prime == 0) { N /= prime; count++; }
            res.push_back({prime, count});
        }
        prime++;
    }
    return res;
}
// Euler's Totient Function - gives no of nos less than x which are coprime with n
//
// $$ TIME: O(sqrt(N) * log(N)) for composite N; O(N) for prime N
ll phi(ll N){
    ll prime = 2, n = N;
    float res = n;
    while (prime * prime <= n){
        if (N % prime == 0){
            while (N % prime == 0){ N /= prime; }
            res *= (1.0 - (1.0 / (float)prime)); // or res -= res / prime
        }
        prime++;
    }
    if (N > 1) { res *= (1.0 - (1.0 / (float)N)); } // or res -= res/N
    return (ll)res;
}
// Computes factorials from last highest previously precomputed factorial to currently asked and all in between.
// $$ TIME: Depends on last precomputed factorial and current number (O(N))
ll X_factorial_mod(ll n, ll m){
	if (n+1>(ll)FACTORIALS.size() && FACTORIALS.size()!=0){
		ll p = FACTORIALS[FACTORIALS.size()-1];
		//FACTORIALS.push_back(p);
		ll i=FACTORIALS.size();
		for(; i<=n; i++) {
			p = (p * i) % m;
			FACTORIALS.push_back(p);
		}
		return p;
	}
	else if (FACTORIALS.size()==0){
		ll p = 1;
		FACTORIALS.push_back(p);
		ll i=FACTORIALS.size();
		for(; i<=n; i++) {
			p = (p * i) % m;
			FACTORIALS.push_back(p);
		}
		return p;
	}
	else {
		return FACTORIALS[n];
	}
}
// Computes a^b efficiently
// $$ TIME: O(log(b))
ll X_power(ll a, ll b){
	if (b == 0) return 1;
	ll res = X_power(a, b/2);
    return (b % 2) ? res * res * a : res * res;
}
// Computes a^b efficiently while keeping answer mod m
// $$ TIME: O(log(b))
ll X_power_mod(ll a, ll b, ll m = LLONG_MAX){
	if (b == 0){ return 1; }
	ll res = X_power_mod(a, b/2, m) % m;
	res = (res * res) % m;
	if (b % 2){
		return (res * a) % m;
	} else {
		return res;
	}
}
// Computes mod inverse of a wrt m, i.e a^-1 mod m; using euclid's extended algorithm; CONDITION: a,m to be coprime
// $$ TIME: O(log(min(a, m))) [NOTE: returns -1 if inverse doesn't exist!]
ll X_mod_inverse(ll a, ll m){
    ll x, y, res;
    ll g = X_gcd_extended(a, m, x, y);
    if (g != 1){
        cout << "Inverse doesn't exist! A and M are not coprime!";
		res = -1;
	} else {
        res = (x % m + m) % m; // m is added to handle negative x
    }
	return res;
}
// uses fermat's little theorum for computing mod inverse of a wrt m; states that a^-1 mod m = a^(m-2) mod m; CONDITION: m to be prime
// $$ TIME: O(log(m))
ll X_mod_inverse_fermat(ll a, ll m){
	//     ll g = X_gcd(a, m);
	//     if (g != 1){
	//         cout << "Inverse doesn't exist! A and M are not coprime!";
	// 	return -1;
	// } else {
	// 	return X_power_mod(a, m - 2, m);
	//     }
    return X_power_mod(a, m - 2, m);
}
// Computes (a / b) mod m; mod inverse of b needs to exist with m (i.e gcd(b,m)=1), else -1 is returned
// $$ TIME: O(log(b))
ll X_mod_division(ll a, ll b, ll m){
    ll inverse = X_mod_inverse(b, m);
    if (inverse == -1) return -1;
    ll modDiv = ((a % m) * inverse) % m;
    if (modDiv < 0) modDiv += m;
    return modDiv;
}
// computes nCr while keeping answer mod m; by computing n!, and mod inverses of r!, (n-1)!
// $$ TIME: O(N) : O(N) for precomputing factorials till n; 2*O(log(m)) for computing 2 mod inverses
ll nCr_mod(ll n, ll r, ll m) {
	ll p = ((X_factorial_mod(n, m) * X_mod_inverse(FACTORIALS[r], m)) % m * X_mod_inverse(FACTORIALS[n-r], m)) % m;
	return p;
}
/////////////////////////////////////////////// END ///////////////////////////////////////////////

/////////////////////////////////////////////// DRIVER CODE ///////////////////////////////////////////////
#ifndef ONLINE_JUDGE
    clock_t tStart = clock();
#endif
void start(); // cpp programs
void generate(int argc, char* argv[]); // generator for stress testing
void computeRuntime(){
    #ifndef ONLINE_JUDGE
        fprintf(stderr, "\n>>> [@mohitdmak]: !OJ_mode: Runtime: %.6fs <<<\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
}
int main(int argc, char* argv[]){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ; cout.tie(NULL);
	// cout.precision(numeric_limits<double>::max_digits10);
    #ifndef ONLINE_JUDGE
        rlimit R;
        getrlimit(RLIMIT_STACK, &R);
        R.rlim_cur = R.rlim_max;
        setrlimit(RLIMIT_STACK, &R);
    #endif
    #ifndef MOHITDMAK_GENERATOR_MODE // flagged within generator
        start();
    #else
        generate(argc, argv); 
    #endif
    #ifndef ONLINE_JUDGE
        #ifndef MOHITDMAK_STRESS_TESTING_MODE // flagged within counter brutes
            computeRuntime();
        #endif
    #endif
	return (0) ;
}
/////////////////////////////////////////////// END ///////////////////////////////////////////////

int n, m, h[200001];

void solve(){
    // error(n, m);
    // for (int i = 0; i <= n; i++) error(i, h[i]);
    auto cmp = [](int i, int j){ return h[i] - m * i > h[j] - m * j; };
    multiset<int, decltype(cmp)> dp(cmp);
    for (int i = 1; i <= n; i++){
        if (h[i] > m * i) continue;
        auto itr = dp.upper_bound(i);
        // error(i, h[i], dp, itr==dp.end());
        if (itr == dp.end()) dp.insert(i);
        else dp.erase(itr), dp.insert(i);
    }
    cout << n - dp.size();
}
 
void start(){
    cin >> n >> m; int i = 0; while (i++ < n) cin >> h[i];
    solve();
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37