Submission #719115

#	Time	Username	Problem	Language	Result	Execution time	Memory
719115		nihaddhuseynli	Global Warming (CEOI18_glo)	C++14	100 / 100	70 ms	25168 KiB

glo

//Bismillahi Rahmanir Rahim
#include <bits/stdc++.h>
using namespace std; 
typedef long long LL;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<string, string> pss;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pll> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;
double EPS = 1e-9;
const int N = 1e5;
const ll inf =1000001;
double PI = acos(-1);
const int MX = 2e5 + 5;
const int MS = 30;
int dirx[4] = { 1,0,-1,0 };
int diry[4] = { 0,1,0,-1 };
ll sx,sy,fx,x,fy,Z,m,n,k,y,ans,f[1000001],b[inf],a[inf],r,res,cur,ans1,flag,flag1,flag2,flag3,flag4,cnt,cnt1,cnt2,cnt3,minn,maxx,maxx1,sum,sum1,ans2,ans3;
vector<ll> adj[200000];
vi z,z1;
char c[505][505];
ll visited[500001],color[500001];
vector<ll> dist;    
ll mat[1001][1001]; 
string str,str1,str2,str3;
const int md = 1e9+7;
vector<vector<pair<int,int>>> g;
vector<pair<ll,ll>>v;
vl v2;
priority_queue<pair<pair<long long, int>, bool> > pq;
map<ll,ll>mp;
map<char,ll>mp1;
queue<ll> q;
set<ll>s;
multiset<LL> ms;
stack<LL>st;
double pi=3.14159265358979323846;
bool ok[505][505];
vector<ll> v1[500001];
bool prime[200001];
vector<char> path;
ll is[N+1];
ll dp[505][505];
ll en[200001],ex[200001],tour[200001],depth[200001],segtree[inf];
ll up[MS][MX];
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define FORD(a, b, c) for (int(a) = (b)-1; (a) >= (c); --(a))
#define FORSQ(a, b, c) for (int(a) = (b); (a) * (a) <= (c); ++(a))
#define FORC(a, b, c) for (char(a) = (b); (a) <= (c); ++(a))
#define FOREACH(a, b) for (auto&(a) : (b))
#define REP(i, n) FOR(i, 0, n)
#define REPN(i, n) FORN(i, 1, n)
#define MAX(a,b) a=max(a,b)
#define MIN(a, b) a = min(a, b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a, b) memset(a, b, sizeof(a))
#define fi first
#define se second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define TC(t) while (t--)
#define ins insert
#define PERMUTE next_permutation
/*********/
ll find_lis(vector<ll> a) {
    vector<ll> dp;
    for (ll i : a) {
        ll pos = lower_bound(dp.begin(), dp.end(), i) - dp.begin();
        if (pos == dp.size()) {
            dp.push_back(i);
        } else {
            dp[pos] = i;
        }
    }
    return dp.size();
}
void solve()
{
    

    cin >> n >> x;
    FOR(i,0,n)
    {
        cin >> y;
        z.pb(y);    
    }
    vector<ll> v(n,INT_MAX);
    FOR(i,0,n)
    {
        ll pos = lower_bound(v.begin(), v.end(), z[i]) - v.begin();
        v[pos]=z[i];
        b[i]=pos+1;
        maxx=max(maxx,b[i]);
    }
    v=vector<ll>(n,INT_MAX);
    for(int i =n-1;i>=0;i--)
    {
        ll pos = lower_bound(v.begin(),v.end(),-z[i]+x) - v.begin();
        maxx=max(maxx,pos+b[i]);
        ll pos1=lower_bound(v.begin(), v.end(), -z[i]) - v.begin();
        v[pos1]=-z[i];
    }
    cout << maxx << endl;

}
 
/*********/
int main()
{       
    ios::sync_with_stdio(0);     
    cin.tie(0);
    int t=1;
    int i =1;
    //cin >> t;
    //freopen("snakes.in", "r", stdin);
    //freopen("snakes.out", "w", stdout); 
    TC(t)
    {
        solve();
    }
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'll find_lis(std::vector<long long int>)':
glo.cpp:80:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         if (pos == dp.size()) {
      |             ~~~~^~~~~~~~~~~~
glo.cpp: In function 'void solve()':
glo.cpp:50:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   50 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                              ^
glo.cpp:93:5: note: in expansion of macro 'FOR'
   93 |     FOR(i,0,n)
      |     ^~~
glo.cpp:50:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   50 | #define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
      |                              ^
glo.cpp:99:5: note: in expansion of macro 'FOR'
   99 |     FOR(i,0,n)
      |     ^~~
glo.cpp: In function 'int main()':
glo.cpp:124:9: warning: unused variable 'i' [-Wunused-variable]
  124 |     int i =1;
      |         ^

• 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