Submission #671407

#TimeUsernameProblemLanguageResultExecution timeMemory
671407Quan2003Global Warming (CEOI18_glo)C++17
10 / 100
414 ms23044 KiB
#include <bits/stdc++.h> #include <iostream> #include<vector> using namespace std; typedef long long ll; const int sz=5e5+10; const int sz1=1e6+1; const int inf=1e9 + 7; const int mod = 1e9 + 7; int n,m,k,w; long long d; long long a[sz]; long long dp[sz]; long long bit[sz]; void upd(int x,int diff){ for (int i = x; i < sz; i |= i + 1) bit[i]= max(bit[i],(1ll)*diff); } long long query(int x){ long long res = 0; for (int i = x; i >= 0; i = (i & (i + 1)) - 1) res = max(res,bit[i]); return res; } int main(){ cin>>n>>d; vector<long long>cor; for(int i = 1; i <= n; i++){ cin>>a[i]; cor.push_back(a[i]); cor.push_back(a[i] + d); cor.push_back(a[i] - d); } map<long long,int>mp; sort(cor.begin(),cor.end()); cor.erase(unique(cor.begin(),cor.end()),cor.end()); for(int i = 0; i < cor.size(); i++) mp[cor[i]] = i + 1; long long ans = 0; for(int i = 1; i <= n; i++){ int down = query(mp[a[i] - d] - 1); int up = query(mp[a[i] + d] - 1); int cur = query(mp[a[i]] - 1); ans = max(ans, (1ll)*max(cur,max(up,down)) + 1); // upd(mp[a[i] - d], 1 + down); upd(mp[a[i]], 1 + cur); // upd(mp[a[i] + d], 1 + up); } cout<<ans<<endl; }

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |      for(int i = 0; i < cor.size(); i++) mp[cor[i]] = i + 1;
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...