제출 #345870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
345870		jenishmonpara	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	32 ms	5992 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
long double PI = acos(-1);
long double DEL = 1e-10;
int M =  1e9 + 7;
const int N = 3e5 + 10;

#define ftt cin>>t;for(int tt=1;tt<=t;++tt)
#define all(a) a.begin(),a.end()
#define vpii vector<pair<int,int>>
#define vvi vector<vector<int>>
#define pii pair<int,int>
#define vi vector<int>
#define sq(a) ((a)*(a))
#define double long double
#define dbg cout<<"\nhi\n";
#define int long long
#define nl cout<<"\n"
#define sp <<" "<<
#define S second
#define F first

int fpow(int x, int n)
{
      int res = 1;
      x %= M;
      while(n)
      {
            if(n&1)res = res * x % M;
            x = x * x % M;
            n>>=1;
      }
      return res;
}
int gcd(int a,int b)
{
      if(b == 0)return a;
      return gcd(b,a % b);
}
int lcm(int a,int b)
{
      return a*(b/gcd(a,b));
}
void create_fac(int n)
{
      vector<int> fac(N),inv(N);
      fac[0] = inv[0] = 1;
      for(int i=1;i<=n;i++)
      {
            fac[i] = fac[i-1]*i % M;
            inv[i] = fpow(fac[i],M-2);
      }
}
int ncr(int n,int r)
{
      vector<int> fac(N),inv(N);
      return fac[n] * (inv[r] * inv[n-r] % M) % M;
      return fac[n] * (fpow(fac[r],M-2) * fpow(fac[n-r],M-2) % M ) % M;
}
void sieve (int n)      // linear sieve
{
      vector <int> primes;
      bool iscomp[N];
      for (int i = 2; i <= n; ++i)
      {
            if (!iscomp[i]) primes.push_back(i);
            for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j)
            {
                  iscomp[i * primes[j]] = true;
                  if (i % primes[j] == 0) break;
            }
      }
}

// you can also use __int128
// priority_queue<int,vector<int>,greater<int>>
// bitset<100>(x).count()
//**************************************** CHECK CONSTRAINTS ***********************************************
int cnt, sum, mid, mx, mn, ans, a[N], b[N];
int n, m, d, i, j, k, l, p, q, r, t, w, x, y, z;
string s;


int32_t main()
{
      ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      cin>>n>>m;
      vi a(n);
      for(int i=0;i<n;i++)
      {
            cin>>a[i];
            a[i] = m*i- a[i];
      }
      vi lis;
      lis.push_back(-m);
      for(auto j:a)
      {
            //cout<<j;nl;
            int pos = upper_bound(all(lis),j) - lis.begin();
            if(pos == 0)continue;
            if(pos == lis.size())lis.emplace_back(j);
            else lis[pos] = j;
      }
      cout<<n-lis.size()+1;
}
/*
 5 400
 300
 700
 200
 1000
 500
 */

컴파일 시 표준 에러 (stderr) 메시지

triusis.cpp: In function 'void sieve(long long int)':
triusis.cpp:67:31: 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]
   67 |             for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j)
      |                             ~~^~~~~~~~~~~~~~~
triusis.cpp: In function 'int32_t main()':
triusis.cpp:101:20: 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]
  101 |             if(pos == lis.size())lis.emplace_back(j);
      |                ~~~~^~~~~~~~~~~~~

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