Submission #716211

#TimeUsernameProblemLanguageResultExecution timeMemory
716211steamEngineRabbit Carrot (LMIO19_triusis)C++17
100 / 100
30 ms7852 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") //#pragma GCC optimize("unroll-loops") #include "bits/stdc++.h" /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define node pair<int,int> #define ordered_set tree<node, null_type,less<node>, rb_tree_tag,tree_order_statistics_node_update> //order_of_key (k) : Number of items strictly smaller than k //find_by_order(k) : K-th element in a set (counting from zero) */ #define db1(x) cout<<#x<<"="<<x<<'\n' #define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n' #define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n' #define ff first #define endl '\n' #define ss second #define int long long #define pb push_back #define mp make_pair #define fr(i, s, e) for(int i = s; i < e; i++) #define rfr(i, s, e) for(int i = s; i >= e; i--) #define geta(a, n) for(int i = 0; i < n; i++) cin >> a[i]; #define pii pair<int,int> #define vi vector<int> #define mii map<int,int> #define pqb priority_queue<int> #define pqs priority_queue<int,vi,greater<int> > #define setbits(x) __builtin_popcountll(x) #define zrobits(x) __builtin_ctzll(x) #define inf 1e18 #define ps(x,y) fixed<<setprecision(y)<<x #define mk(arr,n,type) type *arr=new type[n]; #define all(x) x.begin(),x.end() #define MOD 1000000007 using namespace std; using ll = long long; // int dx[]={-1,1,0,0}; int dy[]={0,0,1,-1}; // int dx[]={2,2,-2,-2,1,1,-1,-1}; int dy[]={1,-1,1,-1,2,-2,2,-2}; /*------------------------------UNORDERED MAP HASH --------------------------------------------*/ //To make unordered_map unhackable // use it as unordered_map<int,int,custom_hash> mapp; /* struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; */ /*------------------------------END--------------------------------------------*/ inline int powMod(int a, int b) { int x = 1; while (b > 0) { if (b & 1) x = (x * a) % MOD; a = (a * a) % MOD; b >>= 1; } return x; } inline int multiply(int x, int y) { return ((x % MOD) * (y % MOD)) % MOD; } inline int divide(int x, int y) { return ((x % MOD) * powMod(y % MOD, MOD - 2)) % MOD; } inline int ceil(int a, int b) { return (a + b - 1) / b; } int gcd (int a, int b) { while (b) { a %= b; swap(a, b); } return a; } int lcm (int a, int b) { return a / gcd(a, b) * b; } int inverseMod(int a, int m) { a = a % m; for (ll x = 1; x < m; x++) if ((a * x) % m == 1) return x; return -1; } #ifdef GAURAVDEBUG #include "C:\Users\gengi\OneDrive\Documents\debug.cpp" #else #define debug(...) "" #endif template<int D, typename T> struct vec : public vector < vec < D - 1, T >> { static_assert(D >= 1, "Vector dimension must be greater than zero!"); template<typename... Args> vec(int n = 0, Args... args) : vector < vec < D - 1, T >> (n, vec < D - 1, T > (args...)) { } }; template<typename T> struct vec<1, T> : public vector<T> { vec(int n = 0, T val = T()) : vector<T>(n, val) { }}; int n,m; void solve() { cin>>n>>m; vector<int> heights(n); vector<int> candis; for(int i=0;i<n;i++) { cin>>heights[i]; int ind=i+1; if(heights[i]-(m*ind)<=0){ candis.pb(abs(heights[i]-(m*ind))); } } vector<int> lcs; for(int i=0;i<candis.size();i++){ if(lcs.empty() || lcs.back()<=candis[i]){ lcs.pb(candis[i]); continue; } else{ auto ptr=upper_bound(all(lcs),candis[i]); *ptr=candis[i]; } } cout<<n-lcs.size()<<endl; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif int t = 1; // cin >> t; while (t--) solve(); return 0; }

Compilation message (stderr)

triusis.cpp: In function 'void solve()':
triusis.cpp:97:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=0;i<candis.size();i++){
      |                 ~^~~~~~~~~~~~~~
triusis.cpp: In function 'int32_t main()':
triusis.cpp:118:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |     freopen("error.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...