제출 #318039

#제출 시각아이디문제언어결과실행 시간메모리
318039DymoGlobal Warming (CEOI18_glo)C++14
58 / 100
450 ms8168 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define eb emplace_back #define ll int #define pll pair<ll,ll> #define ff first #define ss second #define endl "\n" const ll maxn=2e5+50; const ll mod =998244353 ; const ll base=3e18; vector<ll> vt; ll st[2][4*maxn]; ll a[maxn]; void update(ll id,ll left,ll right,ll x,ll diff,ll t ) { if (x>right||x<left) return ; if (right==left ) { st[t][id]=max(st[t][id],diff); return ; } ll mid=(left+right)/2; update(id*2,left,mid, x, diff,t); update(id*2+1, mid+1, right, x, diff,t); st[t][id]=max(st[t][id*2],st[t][id*2+1]); } ll get(ll id,ll left,ll right,ll x,ll y,ll t) { if (x>right||y<left||x> y) return 0; if (x<=left&&y>=right) { return st[t][id]; } ll mid=(left+right)/2; return max(get(id*2,left,mid, x, y, t ),get(id*2+1, mid+1, right, x, y, t)); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n, x ; cin>> n>> x ; vt.pb(-1e15); for (int i=1;i<=n;i++) { cin>>a[i]; vt.pb(a[i]); vt.pb(a[i]-x); } sort(vt.begin(),vt.end()); vt.resize(unique(vt.begin(),vt.end())-vt.begin()); ll ans=0; //cout <<vt.size()<<endl; /*for (auto to:vt) { cout <<to<<endl; }*/ for (int i=1;i<=n;i++) { ll h=lower_bound(vt.begin(),vt.end(),a[i])-vt.begin(); ll t=get(1,1,vt.size()-1,1,h-1,0)+1; // cout <<1<<" "<<1<<" "<<vt.size()-1<<" "<<1<<" "<<h-1<<" "<<0<<endl; ll p=get(1,1,vt.size()-1,1,h-1,1)+1; update(1,1,vt.size()-1,h,t,0); // cout <<1<<" "<<1<<" "<<vt.size()<<" update(1,1,vt.size()-1,h,p,1); ll h1=lower_bound(vt.begin(),vt.end(),a[i]-x)-vt.begin(); update(1,1,vt.size()-1,h1,t,1); //cout <<t<<" "<<p<<" "<<h<<endl; // cout <<h<<" "<<h-1<<endl; ans=max(ans,t); ans=max(ans,p); } //update(1,1,vt.size()-1,4,2,0); // cout <<get(1,1,vt.size()-1,1,3,0)<<endl ; cout <<ans<<endl; /*10 10 1 1 1 1 1 1 2 2 2 1 */ }

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

glo.cpp:15:15: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   15 | const ll base=3e18;
      |               ^~~~
glo.cpp: In function 'int main()':
glo.cpp:52:11: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '-1.0e+15' to '-2147483648' [-Woverflow]
   52 |     vt.pb(-1e15);
      |           ^~~~~
#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...