Submission #760644

#	Time	Username	Problem	Language	Result	Execution time	Memory
760644		karthiksing05	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	320 KiB

triusis

/*
Problem URL:
https://oj.uz/problem/view/LMIO19_triusis
*/
 
#include <bits/stdc++.h>
 
using namespace std;
 
void setIO(string s = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (s != "") {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
  }
}
 
// DEBUG INFO:
 
// helper for printing a pair
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
 
// helper for printing a container
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}
 
// SHORTENED MACROS
#define ll long long
#define ull unsigned long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
#define MOD 1000000007
#define x first
#define y second
 
// VERY USEFUL ORDERED CONTAINER TO USE INSTEAD OF STL
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(x)                                                         \
  tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset(x)                                                    \
  tree<x, null_type, less_equal<x>, rb_tree_tag, tree_order_statistics_node_update>

// Number Theory Stuff

// Modular Exponentiation in O(log(M)) time
ll modExp(ll x, ll n, ll m) {
	assert(n >= 0);
	x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
	return res;
}

// Modular Inverse in < O(log(M)) time
int modInv(int i, int m) {
  return i <= 1 ? i : m - (long long)(m/i) * modInv(m % i, m) % m;
}

// ModInt convenience template that automatically wraps around the set MOD
struct mi {
	int v;
	explicit operator int() const { return v; }
	mi() { v = 0; }
	mi(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; }
};
mi &operator+=(mi &a, mi b) {
	if ((a.v += b.v) >= MOD) a.v -= MOD;
	return a;
}
mi &operator-=(mi &a, mi b) {
	if ((a.v -= b.v) < 0) a.v += MOD;
	return a;
}
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((long long)a.v * b.v); }
mi &operator*=(mi &a, mi b) { return a = a * b; }
mi pow(mi a, long long p) {
	assert(p >= 0);
	return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1);
}
mi inv(mi a) {
	assert(a.v != 0);
	return pow(a, MOD - 2);
}
mi operator/(mi a, mi b) { return a * inv(b); }

/*
 
Useful Links:
 
- the below link matches time complexity with input size
https://codeforces.com/blog/entry/21344
 
Problems to review for Silver:
https://codeforces.com/problemset?tags=combine-tags-by-or,binary%20search,data%20structures,two%20pointers,1700-2000

REALLY GOOD PROOFING WIKI:
http://zimmer.csufresno.edu/~larryc/proofs/proofs.html

CodeDrills Problem Recommender:
- https://recommender.codedrills.io/profile?handles=karthiksing05

DO THESE FOR BITWISE OPS PRACTICE:
https://codeforces.com/gym/344975

Brainstorming:
 
Important Info:
- 

Thoughts:
- can we just solve this greedily?
- move all poles that need to be moved and keep them as high as possible,
  because there's no penalty for that
  
- we can just calculate all gaps between for which the distance (with sign) is
  greater than M, right?
  
- where in the world will LIS ever come into play??

*/

int N, M;
vector<int> poles;

int main(void) {
  
  setIO();
  
  cin >> N >> M;
  
  poles.push_back(0);
  
  for (int i = 0; i < N; i++) {
    poles.push_back(0);
    cin >> poles[i + 1];
  }
  
  poles.push_back(0);
  
  int ans = 0;
  
  for (int i = 0; i <= N; i++) {
    if (poles[i + 1] - poles[i] > M) {
      poles[i + 1] = poles[i] + M;
      ans++;
    }
  }
  
  cout << ans << "\n";
  return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'void setIO(std::string)':
triusis.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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