Submission #346330

#	Time	Username	Problem	Language	Result	Execution time	Memory
346330		jenishmonpara	Global Warming (CEOI18_glo)	C++14	100 / 100	68 ms	7912 KiB

glo

#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[N], p, q, r[N], t, w, x, y, z;
string s;


int32_t main()
{
      ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      cin>>n>>x;
      for(int i=1;i<=n;i++)cin>>a[i];
      vi lis;
      for(int i=1;i<=n;i++)
      {
            int pos = lower_bound(all(lis),a[i]) - lis.begin();
            if(pos == lis.size())lis.push_back(a[i]);
            lis[pos] = a[i];
            l[i] = pos + 1;
      }
      ans = 0;
      lis.clear();
      for(int i=n;i>0;i--)
      {
            int pos = lower_bound(all(lis),-a[i]+x) - lis.begin();
            r[i] = pos;
            pos = lower_bound(all(lis),-a[i]) - lis.begin();
            if(pos == lis.size())lis.push_back(-a[i]);
            lis[pos] = -a[i];
            ans = max(ans,r[i] + l[i]);
            //cout<<i sp l[i] sp r[i];nl;
      }
      cout<<ans;
}

/*
 8 10
 7 3 5 12 2 7 3 4

 */

Compilation message (stderr)

glo.cpp: In function 'void sieve(long long int)':
glo.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)
      |                             ~~^~~~~~~~~~~~~~~
glo.cpp: In function 'int32_t main()':
glo.cpp:93: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]
   93 |             if(pos == lis.size())lis.push_back(a[i]);
      |                ~~~~^~~~~~~~~~~~~
glo.cpp:104: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]
  104 |             if(pos == lis.size())lis.push_back(-a[i]);
      |                ~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25