AtCoder 競技プログラミングの鉄則　演習問題集 C15問題 - Many Meetings

Source

AtCoder 競技プログラミングの鉄則　演習問題集
問題文

問題概要

省略

解法

省略

cLay（version 20221122-1）のコード

C++に変換後のコードはこちら

int @N, @K; int L[N], R[N], ind[N], res[N]; rd((L,R)(N));

int i, j, k, sz;
rep(i,N) ind[i] = i;
rep(i,N) R[i] += K;
sortA(N,L,R,ind);

int dp1[2d5] = {}, dp2[2d5] = {};

k = 0;
rep(i,N){
  while(k < L[i]) dp1[k+1] >?= dp1[k], k++;
  dp1[R[i]] >?= dp1[L[i]] + 1;
}

k = 2d5-1;
rrep(i,N){
  while(k > R[i]) dp2[k-1] >?= dp2[k], k--;
  dp2[L[i]] >?= dp2[R[i]] + 1;
}

rep(i,N) res[ind[i]] = dp1[L[i]] + dp2[R[i]] + 1;
wtLn(res(N));

cLay（version 20221122-1）のコード

C++に変換後のコードはこちら

int @N, @K; int L[N], R[N]; rd((L,R)(N));
rep(i,N) R[i] += K;

int dp1[2d5] = {}, dp2[2d5] = {}, go1[2d5], go2[2d5];

rep(i,2d5) go1[i] = int_inf, go2[i] = -int_inf;
rep(i,N) go1[L[i]] <?= R[i];
rep(i,N) go2[R[i]] >?= L[i];

rep(i,2d5-1){
  dp1[i+1] >?= dp1[i];
  if(go1[i] < int_inf) dp1[go1[i]] >?= dp1[i] + 1;
}
rrep(i,2d5-1){
  dp2[i] >?= dp2[i+1];
  if(go2[i] >= 0) dp2[go2[i]] >?= dp2[i] + 1;
}

rep(i,N) wt(dp1[L[i]] + dp2[R[i]] + 1);

Current time: 2024年05月06日03時39分20秒
Last modified: 2022年11月23日10時57分39秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：