(补)双指针专题

M - Letters

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){
    return (a%mod+mod)%mod;}
LL lowbit(LL x){
    return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {
    LL ans = 1; while(b){
     if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n,m;
const int N=2e5+10;
int a[N],b[N];
int s[N];
void solve()
{
    
	cin>>n>>m; 
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	for(int i=1;i<=m;i++)cin>>b[i];
	for(int i=1;i<=m;i++)
	{
    
		int l=0,r=n;
		while(l<r)
		{
    
			int mid=l+r+1>>1;
			if(s[mid]<=b[i])l=mid;
			else r=mid-1;
		}
		if(s[l]!=b[i])
		cout<<l+1<<' '<<b[i]-s[l]<<endl;
		else cout<<l<<' '<<s[l]-s[l-1]<<endl;
	}
}
signed main()
{
    
    io;
 	//cin>>_; 
	//while(_--)
    solve();
    return 0;
}

N - Kirill And The Game

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){
    return (a%mod+mod)%mod;}
LL lowbit(LL x){
    return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {
    LL ans = 1; while(b){
     if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int l,r,x,y,k;
void solve()
{
    
	cin>>l>>r>>x>>y>>k;
	for(int i=x;i<=y;i++)
	{
    
		int left=l,right=r;
		while(left<right)
		{
    
			int mid=left+right>>1;
			if(mid>=k*i)right=mid;
			else left=mid+1;
		}
		if(i*k==left)
		{
    
			cout<<"YES"<<endl;
			return;
		}
	}
	cout<<"NO"<<endl;
}
signed main()
{
    
    io;
 	//cin>>_; 
	//while(_--)
    solve();
    return 0;
}

O - Sereja and Dima

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    
	int n;
	cin>>n;
	vector<int>v;
	for(int i=0;i<n;i++)
	{
    
		int x;
		cin>>x;
		v.push_back(x);
	}
	int a=0,b=0;
	int l=0,r=v.size()-1;
	while(l<=r)
	{
    
		if(l<=r&&v[l]<v[r])a+=v[r--];
		else if(l<=r)a+=v[l++];
		if(l<=r&&v[l]<v[r])b+=v[r--];
		else if(l<=r)b+=v[l++];
	}
	cout<<a<<' '<<b<<endl;
	return 0;
}

P - Alice, Bob and Chocolate

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
#define x first
#define y second
#define LL long long 
#define int LL
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
LL Mod(LL a,LL mod){
    return (a%mod+mod)%mod;}
LL lowbit(LL x){
    return x&-x;}//最低位1及其后面的0构成的数值
LL qmi(LL a,LL b,LL mod) {
    LL ans = 1; while(b){
     if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; }
int _;
int n;
const int N=1e5+10;
int a[N];
int s[N];
void solve()
{
    
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	vector<PII>v;
	for(int i=1;i<=n;i++)
	{
    
		int x=s[i],y=s[n]-s[i];
		if(x-a[i]>y||y-a[i+1]>x)continue;
		else v.pb({
    i,n-i});
	}
	int m=v.size()-1;
	cout<<v[m].x<<' '<<v[m].y<<endl;
	return;
}
signed main()
{
    
    io;
 	//cin>>_; 
	//while(_--)
    solve();
    return 0;
}