Submission #72922

#	Time	Username	Problem	Language	Result	Execution time	Memory
72922		duckmoon99	Lottery (CEOI18_lot)	C++14	0 / 100	5 ms	612 KiB

lot

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18
#define ret return

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll a[222222];
ll b[222222];
int ans1[222222];
int ans2[222222];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    ll x;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
		cin >> a[i];
	}
		vector <ll> LIS;
		for(int i = 0; i < n; i++){
			if(LIS.empty()){
				LIS.pb(a[i]);
			}
			else{
				if(LIS[LIS.size()-1]<a[i]){
					LIS.pb(a[i]);
				}
				else{
					*lower_bound(LIS.begin(),LIS.end(),a[i])=a[i];
				}
			}
			ans1[i]=LIS.size();
		}
		vector <ll> LISS;
		for(int i = 0; i < n; i++){
			if(LISS.empty()){
				LISS.pb(-a[n-1-i]);
			}
			else{
				if(LISS[LISS.size()-1]<-a[n-1-i]){
					LISS.pb(-a[n-1-i]);
				}
				else{
					*lower_bound(LISS.begin(),LISS.end(),-a[n-1-i])=-a[n-1-i];
				}
			}
			ans2[n-i-1]=LISS.size();
		}
		int tans = max(ans2[0],ans1[n-1]);
		/*for(int i = 0; i < n; i++){
			cout << '*' << ans2[i] << endl;
		}*/
		for(int i = 0; i < n-1; i++){
			tans=max(tans,ans1[i]+ans2[i+1]);
		}
		cout << tans;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20