Submission #99093

#	Time	Username	Problem	Language	Result	Execution time	Memory
99093		nishkarsh	Global Warming (CEOI18_glo)	C++14	17 / 100	462 ms	8336 KiB

glo

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
#define INF 2e9
#define INFLL 4e18
#define fr(x,a,b,c) for(int x = a; x <= b; x+=c)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
	ll ans=1;base%=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int upperlimit = 2e5+1;
const int mod = 1e9+7;
struct data{
	int ind,val;
};
bool cmp(data a,data b){
	if(a.val==b.val) return(a.ind>b.ind);
	return (a.val<b.val);
}
data arr[upperlimit];
int ans[upperlimit];
int indices[upperlimit];
int temp[upperlimit];
int segtree[4*upperlimit];
int segtree2[4*upperlimit];
void update(int node,int i,int j,int ind,int val){
	if(i==j){
		segtree[node]=val;
		return;
	}
	int mid=(i+j)/2;
	if(ind<=mid) update(2*node,i,mid,ind,val);
	else update(2*node+1,mid+1,j,ind,val);
	segtree[node]=max(segtree[2*node],segtree[2*node+1]);
}
int query(int node,int i,int j,int l,int r){
	if((i>r)||(l>j)||(i>j)||(l>r)) return 0;
	if((i>=l)&&(j<=r)) return segtree[node];
	int mid=(i+j)/2;
	return max(query(2*node,i,mid,l,r),query(2*node+1,mid+1,j,l,r));
}
void update2(int node,int i,int j,int ind,int val){
	if(i==j){
		segtree2[node]=val;
		return;
	}
	int mid=(i+j)/2;
	if(ind<=mid) update2(2*node,i,mid,ind,val);
	else update2(2*node+1,mid+1,j,ind,val);
	segtree2[node]=max(segtree2[2*node],segtree2[2*node+1]);
}
int query2(int node,int i,int j,int l,int r){
	if((i>r)||(l>j)||(i>j)||(l>r)) return 0;
	if((i>=l)&&(j<=r)) return segtree2[node];
	int mid=(i+j)/2;
	return max(query2(2*node,i,mid,l,r),query2(2*node+1,mid+1,j,l,r));
}
int main(){
	int n,x;
	sd(n);sd(x);
	for(int i = 1; i <= n; i++){
		sd(arr[i].val);arr[i].ind=i;
	}
	temp[0]=INF;
	int mlen=0;
	for(int i = n; i >= 1; i--){
		if(temp[mlen]>arr[i].val){
			mlen++;
			temp[mlen]=arr[i].val;
			ans[i]=mlen;
			continue;
		}
		int l=0,r=mlen;
		while(r-l>1){
			int mid=(l+r)/2;
			if(temp[mid]<=arr[i].val) r=mid;
			else l=mid;
		}
		temp[r]=arr[i].val;
		ans[i]=mlen;
	}
	sort(arr+1,arr+n+1,cmp);
	for(int i = 1; i <= n; i++){
		int k=query(1,1,n,1,arr[i].ind);
		k++;
		update(1,1,n,arr[i].ind,k);
		update2(1,1,n,i,k);
		indices[arr[i].ind]=i;
	}
	int ans2=0;
	for(int i = n; i >= 1; i--){
		int l=1,r=n+1;
		int k=arr[indices[i]].val;k+=x;
		update2(1,1,n,indices[i],0);
		while(r-l>1){
			int mid=(l+r)/2;
			if(arr[mid].val>=k) r=mid;
			else l=mid;
		}
		ans2=max(ans2,query2(1,1,n,1,l)+ans[i]);
	}
	pd(ans2);
	return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:12:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d",&x)
               ~~~~~^~~~~~~~~
glo.cpp:86:2: note: in expansion of macro 'sd'
  sd(n);sd(x);
  ^~
glo.cpp:12:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d",&x)
               ~~~~~^~~~~~~~~
glo.cpp:86:8: note: in expansion of macro 'sd'
  sd(n);sd(x);
        ^~
glo.cpp:12:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d",&x)
               ~~~~~^~~~~~~~~
glo.cpp:88:3: note: in expansion of macro 'sd'
   sd(arr[i].val);arr[i].ind=i;
   ^~

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