제출 #1197289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197289		Batorgil952	Bouquet (EGOI24_bouquet)	C++20	100 / 100	101 ms	15752 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

const int N=2e5+5;
int l[N], r[N];
int dp[N];
vector< int > u[N];
int tree[4*N];

void update(int v, int l, int r, int p, int x){
	if(p<l || p>r) return;
	if(l==p && p==r){
		tree[v]=x;
	}
	else{
		int mid=(l+r)/2;
		update(2*v, l, mid, p, x);
		update(2*v+1, mid+1, r, p, x);
		tree[v]=max(tree[2*v], tree[2*v+1]);
	}
}

int query(int v, int l, int r, int p){
	if(p<l) return 0;
	if(r<=p){
		return tree[v];
	}
	int mid=(l+r)/2;
	return max(query(2*v, l, mid, p), query(2*v+1, mid+1, r, p));
}

int main(){
	int n, i, j, un, ans;
	
	scanf("%d",&n);
	
	for(i=1; i<=n; i++){
		scanf("%d",&l[i]);
		scanf("%d",&r[i]);
		r[i]=min(i+r[i], n);
		l[i]=max(1, i-l[i]);
		u[r[i]+1].pb(i);
	}
	
	dp[0]=0;
	ans=0;
	for(i=1; i<=n; i++){
		un=u[i].size();
		for(j=0; j<un; j++){
			update(1, 1, n, u[i][j], dp[u[i][j]]);
		}
		dp[i]=query(1, 1, n, l[i]-1)+1;
		ans=max(ans, dp[i]);
	}
	
	printf("%d\n", ans);
	
	return 0;
}

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

Main.cpp: In function 'int main()':
Main.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
Main.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |                 scanf("%d",&l[i]);
      |                 ~~~~~^~~~~~~~~~~~
Main.cpp:45:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |                 scanf("%d",&r[i]);
      |                 ~~~~~^~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30