제출 #886648

#제출 시각아이디문제언어결과실행 시간메모리
886648CaubethieunangGlobal Warming (CEOI18_glo)C++17
58 / 100
215 ms15112 KiB
#include <bits/stdc++.h> #define ll long long #define LOG 19 #define MASK(i) (1LL<<(i)) #define BIT(x,i) (((x)>>(i))&1) #define FIRST_BIT(mask) __builtin_ctz((mask)&(-mask)) #define ERASE_BIT(mask) (mask)^((mask)&(-mask)) #define left _left #define right _right #define task "t" using namespace std; const ll INF=1e18; const int iat=1e6+9; const int mod=1e9+7; void fast_IO() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } } int n,x,t[iat],tx[iat],sz,store[iat]; void compress() { vector <int> v; for(int i=1; i<=n; i++) { v.push_back(t[i]); v.push_back(t[i]+x); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); sz=v.size(); for(int i=1; i<=n; i++) { tx[i]=lower_bound(v.begin(),v.end(),t[i]+x)-v.begin()+1; t[i]=lower_bound(v.begin(),v.end(),t[i])-v.begin()+1; } } struct Segment { int st[iat]; void init() { memset(st,0,sizeof(st)); } void update(int id, int l, int r, int pos, int val) { if(l==r) { st[id]=max(st[id],val); return; } int mid=(l+r)/2; if(pos<=mid)update(2*id,l,mid,pos,val); else update(2*id+1,mid+1,r,pos,val); st[id]=max(st[2*id],st[2*id+1]); } int getMax(int id, int l, int r, int u, int v) { if(l>v || r<u)return 0; if(u<=l && r<=v)return st[id]; int mid=(l+r)/2; return max(getMax(2*id,l,mid,u,v),getMax(2*id+1,mid+1,r,u,v)); } }tree; signed main() { fast_IO(); cin>>n>>x; for(int i=1; i<=n; i++)cin>>t[i]; compress(); int ans=0; for(int i=n; i>=1; i--) { store[i]=tree.getMax(1,1,sz,tx[i]+1,sz)+1; tree.update(1,1,sz,tx[i],store[i]); ans=max(ans,store[i]); } tree.init(); for(int i=1; i<=n; i++) { ans=max(ans,store[i]+tree.getMax(1,1,sz,1,tx[i]-1)); int tmp=tree.getMax(1,1,sz,1,t[i]-1)+1; tree.update(1,1,sz,t[i],tmp); ans=max(ans,tmp); } cout<<ans; }

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

glo.cpp: In function 'void fast_IO()':
glo.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
glo.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...