Codeforces Round #310 (Div. 1) A B C

A Case of Matryoshkas
n個の套娃、何組かセットして、毎秒1回の操作を行うことができて、簡単に言えばセットは単一をセットすることしかできなくて、任意に分割して、すべてのセットに一緒に何秒かかるかを聞きます.水の問題は、意味の穴です.

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int m[100010];
int cnt[100010];

int main(){
	int n,k;
	cin>>n>>k;
	int ans=0;
	int MAX=0;
	for(int i=1;i<=k;i++){
		scanf("%d",&m[i]);
		int pre=0;
		int num;
		for(int j=1;j<=m[i];j++){
			scanf("%d",&num);
			if(num==pre+1){
				cnt[i]++;
				pre=num;
			}
			MAX=max(MAX,cnt[i]);
		}
		ans+=m[i]*2;
		ans--;
	}
	ans-=MAX;
	ans-=(MAX-1);
	cout<<ans<<endl;
	
	return 0;
}

B Case of Fugitive
n個の交差しない区間、m個の既知の長さの橋.2つの隣接区間ごとに1つの橋にまたがることが要求される.任意の解を出力し、0を出力しません.
欲張る.各グループの隣接する区間は、必要な橋の上下境界が既知であり、上界昇順に並べられ、最も短い橋を順番に二分して渡せばよい.

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn=200010;

ll l[maxn];
ll r[maxn];
ll a[maxn];
int n,m;

int ans[maxn];

struct node{
	ll MIN;
	ll MAX;
	int id;
	bool operator<(const node other)const{
		return MAX<other.MAX;
	} 
}seg[maxn];

struct Bridge{
	ll len;
	int id;
	bool operator<(const Bridge other)const{
		if(len!=other.len)return len<other.len;
		return id<other.id;
	} 
};

int main(){
	cin>>n>>m;
	
	for(int i=0;i<n;i++){
		scanf("%I64d%I64d",&l[i],&r[i]);
	}
	for(int i=0;i<n-1;i++){
		seg[i].MIN=l[i+1]-r[i];
		seg[i].MAX=r[i+1]-l[i];
		seg[i].id=i;
	}
	
	set<Bridge> Set;
	Bridge bb;
	for(int i=0;i<m;i++){
		scanf("%I64d",&bb.len);
		bb.id=i;
		Set.insert(bb);
	}
	sort(seg,seg+n-1);

	bool ok=1;
	for(int i=0;i<n-1;i++){
		Bridge tmp;	tmp.len=seg[i].MIN;
		tmp.id=-1;
		set<Bridge>::iterator it=Set.lower_bound(tmp);
		if((*it).len>seg[i].MAX){
			ok=0;
			break;
		}else{
			ans[seg[i].id]=it->id;
			Set.erase(*it);
		}
	}
	
	if(ok){
		cout<<"Yes"<<endl;
		for(int i=0;i<n-1;i++){
			printf("%d ",ans[i]+1);
		}
	}else{
		cout<<"No"<<endl;
	}
	
	return 0;
}

C Case of Chocolate
n*nのメッシュ状のチョコレートを1枚、下三角を食べて、上三角(x+y<=n+1)しか残っていません.q回の操作があり、斜線(x+y=n+1)の1つの格子を指定するたびに、上または左に食べ始め、食べられないまで食べます.毎回質問に答えるたびに何個のチェックを食べましたか.
最初は問題を見ていなかったので、二次元線分樹の神問題かと思ったら、食べ始めた点が斜線にあることに気づきました...問題を解く鍵は情報を巧みに維持することだ.毎回食べる格子のx座標を1つのsetに保存して、毎回尋ねることに対して、上へ食べるならば、xが大きいのはいつで、y座標の差を計算します;さもないとxが小さいのはいつで、x座標の差を計算します.そしてyやxを維持しなければならないので、とても巧みです.の

#include <bits/stdc++.h>    
  
using namespace std;    

#define mp make_pair
#define pii pair<int,int>

const int maxn=200010;

int x[maxn];
int y[maxn];

int main(){
	int n,q;
	char dir[2];
	cin>>n>>q;
	set<pii> s;	set<pii>::iterator it;
	s.insert(mp(0,q+1));	x[q+1]=0;	y[q+1]=n+1;
	s.insert(mp(n+1,q+2));	x[q+2]=n+1;	y[q+2]=0;
	for(int i=1;i<=q;i++){
		scanf("%d%d%s",&x[i],&y[i],dir);
		if(dir[0]=='L'){	//    
			it = s.upper_bound(mp(x[i]+1,0));
			it--;
		}else{				//    
			it = s.lower_bound(mp(x[i],0));
		}
		if(it->first==x[i]){
			printf("0
");
			continue;
		}
		s.insert(mp(x[i],i));
		if(dir[0]=='L'){
			printf("%d
",x[i]-x[it->second]);
			x[i]=x[it->second];
		}else{
			printf("%d
",y[i]-y[it->second]);
			y[i]=y[it->second];
		}
	}
	return 0;
}