AC源Day7模拟赛复盘

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;

int n,j=1,f=1;
int p,cnt=0,num[N];
int type[N];

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>p;
	for(int i=1;i<=n;i++){
		cin>>type[i]>>num[i];
	}
	
	while(p<=n && p>0){
		if(type[p]==1 && j>=num[p]){
			cnt++;
			type[p]=(-1);
		}
		else if(type[p]==0){
			j+=num[p];
			f*=(-1);
		}
		
		if((double)clock()/CLOCKS_PER_SEC > 1.9){
			cout<<cnt;
			return 0;
		}
		p+=j*f;
	}
	cout<<cnt;
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;

int n,m;
int t[N],s[N],cnt=0;
vector<int> v;
map<int,int> mp;

int search(int u,int l,int r){
	if(v[n]<u) return n+1;
	if(l==r) return l;
	int mid=(l+r)/2;
	if(u==v[mid]) return mid;
	else if(u>v[mid]) return search(u,mid+1,r);
	else return search(u,l,mid);
}

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>t[i];
	}
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		t[i]-=x+1;
	}
	for(int i=1;i<=n;i++) mp[t[i]]++;
	v.push_back(-1);
	for(auto i:mp){
		if(i.first<0) continue;
		v.push_back(i.first);
		cnt++;
	}
	n=cnt;
	for(int i=n;i>=1;i--){
		s[i]=s[i+1]+mp[v[i]];
	}
	
	for(int i=1;i<=m;i++){
		int tmp,v;
		cin>>v>>tmp;
		if(s[search(tmp,1,n)]>=v) cout<<"YES\n";
		else cout<<"NO\n";
	}
	
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define N 300005
#define mamba return
#define out 0
using namespace std;

const int w=300005;
int n,maxn=0x3f3f3f3f,vn;
bool now[N];
string cinn;
vector<int> t;

void init(){
	int cnt=0;
	for(int i=1;i<=n+1;i++){
		if(now[i]) cnt++;
		else if(cnt>0){
			t.push_back(cnt);
			cnt=0;
		}
	}
	vn=t.size()-1;
}
int max_moon(int u,int p){
	if(u==0) return 0x3f3f3f3f;
	if((p==1 && now[1]) || (p==vn && now[n])){
		return u-1;
	}
	else{
		if(u%2==0) u--;
		return u/2;
	}
}
int check(int u,int d){
	if(u==0) return 0;
	if(d==0) return u;
	int l=1,r=u,minn=0x3f3f3f3f;
	while(l<r){
		int mid=(l+r)/2;
		if(mid+mid*d*2>=u){
			minn=min(minn,mid);
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	return minn;
}

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>cinn;
	t.push_back(0);
	for(int i=0;i<n;i++){
		now[i+1]=(cinn[i]=='1');
	}
	init();
	if(vn==0){
		cout<<0;
		return 0;
	}
	
	
	for(int i=1;i<=vn;i++){
		maxn=min(maxn,max_moon(t[i],i));
	}
	int ans=0;
	for(int i=1;i<=vn;i++){
		ans+=check(t[i],maxn);
	}
	cout<<ans;
	mamba out;
}