2024-1-13 DAY4

B - Integral Array

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e6 + 10;
int n,c;

void solve()
{
 	cin >> n >> c;
 	vector<int> cnt(c*2,0);
 	for(int i=1;i<=n;i++)
 	{
 		int x;
 		cin >> x;
 		cnt[x] ++;
 	}

 	for(int i=1;i<=2*c;i++) cnt[i] += cnt[i-1];

 	for(int i=1;i<=c;i++) 
 	{
 		if(cnt[i]-cnt[i-1]) continue;
 		for(int y=1;y*i<=c;y++)
 		{
 			if((cnt[y]-cnt[y-1])&&(cnt[y*(i+1)-1]-cnt[y*i-1]))
 			{
 				cout << "NO" <<endl;
 				return;
 			}
 		}
 	}
 	cout << "YES" <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

1644D - Cross Coloring

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e6 + 10;
const int mod = 998244353;
int n,m,k,q;

void solve()
{
 	cin >> n >> m >> k >> q;
 	long long ans = 1;
 	set<int> a,b;
 	vector<pair<int,int>> path(q);
 	for(auto &[x,y]:path) cin >> x >> y;
 	reverse(path.begin(),path.end());
 
 	int cntn=0,cntm=0;
 	for(auto [x,y]:path)
 	{
 		bool ok=false;
 		if(a.find(x)==a.end())
 		{
 			ok=true;
 			cntn++;
 		}
 		if(b.find(y)==b.end())
 		{
 			cntm++;
 			ok=true;
 		}
 		if(ok) ans = ans * k % mod;
 		if(cntn==n||cntm==m) break;
 		a.insert(x);
 		b.insert(y);
 	}
 	cout << ans <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

1394A - Boboniu Chats with Du

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n,d,m;
int p1[N],p2[N];
void solve()
{
	cin >> n >> d >>m;
	vector<int> a,b;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin >> x;
		if(x>m) a.push_back(x);
		else    b.push_back(x);
	}
	sort(a.begin(),a.end(),greater<int>());
	sort(b.begin(),b.end(),greater<int>());
	for(int i=1;i<=a.size();i++) p1[i] = p1[i-1] + a[i-1];
	for(int i=1;i<=b.size();i++) p2[i] = p2[i-1] + b[i-1];	
	int ans = p2[b.size()];

	for(int i=1;i<=a.size();i++)
	{
		int sum = p1[i];
		int len = (i-1)*d;
		len -= min((int)a.size()-i,len);
		len = b.size() - len;
		if(len<0) continue;
		sum += p2[len];
		ans = max(ans,sum);
	}
	cout << ans <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) solve();
    return 0;
}