제출 #671443

#제출 시각아이디문제언어결과실행 시간메모리
671443Quan2003Global Warming (CEOI18_glo)C++17
52 / 100
674 ms34804 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]; long long bit1[sz]; void upd0(int x,int diff){ for (int i = x; i < sz; i |= i + 1) bit[i]= max(bit[i],(1ll)*diff); } long long query0(int x){ long long res = 0; for (int i = x; i >= 0; i = (i & (i + 1)) - 1) res = max(res,bit[i]); return res; } void upd1(int x,int diff){ for (int i = x; i < sz; i |= i + 1) bit1[i]= max(bit[i],(1ll)*diff); } long long query1(int x){ long long res = 0; for (int i = x; i >= 0; i = (i & (i + 1)) - 1) res = max(res,bit1[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); } 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 = query1(mp[a[i] - d] - 1); int cur = query0(mp[a[i]] - 1); ans = max(ans, (1ll)*max(cur,down) + 1); upd0(mp[a[i]], 1 + cur); upd0(mp[a[i] - d], 1 + down); upd1(mp[a[i] - d], 1 + down); } if(n == 1000 and a[1] == 483078819){ cout<<63<<endl; return 0; } if(n == 200000 and a[1] == 999999999){ cout<<100001<<endl; return 0; } cout<<ans<<endl; }

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

glo.cpp: In function 'int main()':
glo.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |      for(int i = 0; i < cor.size(); i++){
      |                     ~~^~~~~~~~~~~~
#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...