Submission #294554

#	Time	Username	Problem	Language	Result	Execution time	Memory
294554		nandonathaniel	Arcade (NOI20_arcade)	C++14	100 / 100	240 ms	22504 KiB

Arcade

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=1e6+5;
int MAX,a[MAXN],T[MAXN],A[MAXN],bit[MAXN];
pii arr[MAXN];

int query(int x){
	int ret=0;
	for(int i=x;i>0;i-=(i&-i)){
		ret=max(ret,bit[i]);
	}
	return ret;
}

void update(int x,int v){
	for(int i=x;i<=MAX;i+=(i&(-i))){
		bit[i]=max(bit[i],v);
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=m;i++)cin >> T[i];
	for(int i=1;i<=m;i++)cin >> A[i];
	for(int i=1;i<=m;i++)arr[i]={A[i]+T[i],-(A[i]-T[i])};
	sort(arr+1,arr+m+1);
	vector<pii> v;
	for(int i=1;i<=m;i++){
		a[i]=-arr[i].second;
		v.push_back({a[i],i});
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		if(i==0 || v[i].first!=v[i-1].first)MAX++;
		a[v[i].second]=MAX;
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		int dp=query(a[i]-1)+1;
		update(a[i],dp);
		ans=max(ans,dp);
	}
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

Arcade.cpp: In function 'int main()':
Arcade.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 14 / 14
• Subtask 6: 20 / 20
• Subtask 7: 15 / 15