Submission #656423

#	Time	Username	Problem	Language	Result	Execution time	Memory
656423		ono_de206	Global Warming (CEOI18_glo)	C++14	62 / 100	100 ms	6324 KiB

glo

#include<bits/stdc++.h>
using namespace std;
 
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

typedef long long ll;
 
//#define int long long

template<typename T>
void mxx(T &a, T b){if(b>a) a=b;}
template<typename T>
void mnn(T &a, T b){if(b<a) a=b;}

const int mxn=2e5+10;

pair<int,int> pre[mxn],suf[mxn];

int a[mxn];

signed main(){
	int n,x;
	cin>>n>>x;
	for(int i=1; i<=n; i++){
		cin>>a[i];
	}
	vector<int> g;
	pre[0]={0,-1e9};
	suf[n+1]={0,1e9};
	for(int i=1; i<=n; i++){
		pre[i]=pre[i-1];
		int gg=lower_bound(all(g),a[i])-g.begin();
		if(gg==g.size()) g.pb(a[i]);
		else g[gg]=a[i];
		mxx(pre[i],{(int)g.size(),-g.back()});
	}
	g.clear();
	for(int i=n; i>=1; i--){
		suf[i]=suf[i+1];
		int gg=lower_bound(all(g),-a[i])-g.begin();
		if(gg==g.size()) g.pb(-a[i]);
		else g[gg]=-a[i];
		mxx(suf[i],{(int)g.size(),-g.back()});
	}
//	for(int i=1; i<=n; i++){
//		cout<<pre[i].ff<<' '<<pre[i].ss<<'\n';
//	}
	int ans=0;
	for(int i=0; i<=n; i++){
		if(-pre[i].ss<suf[i+1].ss) mxx(ans,pre[i].ff+suf[i+1].ff);
		else if(-pre[i].ss-suf[i+1].ss+1<=x) mxx(ans,pre[i].ff+suf[i+1].ff);
	}
	cout<<ans<<'\n';
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:39:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   if(gg==g.size()) g.pb(a[i]);
      |      ~~^~~~~~~~~~
glo.cpp:47:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   if(gg==g.size()) g.pb(-a[i]);
      |      ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25