CSES - Putka Open 2025 – 2/5

Submission details
Task:	Ryhmät
Sender:	Laakeri
Submission time:	2025-09-27 12:39:36 +0300
Language:	C++ (C++11)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	15
#3	ACCEPTED	75

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 3	details
#2	ACCEPTED	0.01 s	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	ACCEPTED	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.04 s	2	details
#7	ACCEPTED	0.07 s	2	details
#8	ACCEPTED	0.29 s	2	details
#9	ACCEPTED	0.01 s	2, 3	details
#10	ACCEPTED	0.08 s	3	details
#11	ACCEPTED	0.08 s	3	details
#12	ACCEPTED	0.08 s	3	details
#13	ACCEPTED	0.07 s	3	details
#14	ACCEPTED	0.22 s	3	details
#15	ACCEPTED	0.25 s	3	details
#16	ACCEPTED	0.11 s	3	details

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;

const int N=1<<17;
int st[2*N];

void add(int i, int x){
	for (i+=N;i;i/=2){
		st[i]+=x;
	}
}

int sum(int a, int b){
	a+=N;
	b+=N;
	int su=0;
	while (a<=b){
		if (a%2){
			su+=st[a++];
		}
		if (b%2==0){
			su+=st[b--];
		}
		a/=2;
		b/=2;
	}
	return su;
}

int steal[N];
int nid[N];
vector<int> ks[N];
int fail[N];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,t;
	cin>>n>>t;
	vector<pair<int, pair<int,int>>> es;
	/*
	1 lapsi alkaa
	2 lapsi loppuu
	3 kysely
	*/
	for (int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;
		es.push_back({a, {1,b}});
		es.push_back({b+1, {2,b}});
	}
	for (int i=0;i<t;i++){
		int m;
		cin>>m;
		for (int j=0;j<m;j++){
			int k;
			cin>>k;
			es.push_back({k, {3,i}});
			ks[i].push_back(k);
		}
		sort(ks[i].begin(), ks[i].end());
	}

	sort(es.begin(), es.end());

	for (auto e : es){
		if (e.S.F==1){
			add(e.S.S, 1);
		} else if (e.S.F==2){
			add(e.S.S, -1);
		} else if (e.S.F==3){
			int id=e.S.S;
			if (fail[id]){
				continue;
			}
			int oid=nid[id]++;
			int nextk=n+1;
			if (oid+1<(int)ks[id].size()){
				nextk=ks[id][oid+1];
			}

			int avail=sum(1,n)-steal[id];
			if (avail<e.F){
				fail[id]=1;
				continue;
			}

			int availnice=sum(1,nextk-1);

			if (availnice >= steal[id] + e.F){
				steal[id]=0;
			} else {
				steal[id] = steal[id] + e.F - availnice;
			}
		}
	}
	for (int i=0;i<t;i++){
		if (fail[i]){
			cout<<"NO"<<endl;
		} else {
			cout<<"YES"<<endl;
		}
	}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 10 10 10 10 6 9 6 8 ...` view save

correct output
`YES YES YES NO YES ...` view save

user output
`YES YES YES NO YES ...` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 9 9 6 10 8 10 8 8 ...` view save

correct output
`NO YES NO YES NO ...` view save

user output
`NO YES NO YES NO ...` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 1 1 1 1 1 1 1 1 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 100 100 100 100 100 100 100 100 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 4 9 3 8 7 9 7 9 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` view save

Test 6

Group: 2

Verdict: ACCEPTED

input
`1000 1000 9 10 2 5 10 10 5 5 ...` view save

correct output
`YES YES YES YES NO ...` view save

user output
`YES YES YES YES NO ...` view save

Test 7

Group: 2

Verdict: ACCEPTED

input
`1000 1000 5 7 9 9 3 7 8 10 ...` view save

correct output
`YES NO NO YES YES ...` view save

user output
`YES NO NO YES YES ...` view save

Test 8

Group: 2

Verdict: ACCEPTED

input
`1000 1000 1 1 1 1 1 1 1 1 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
`1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 10

Group: 3

Verdict: ACCEPTED

input
`100000 1000 774 778 363 852 309 668 261 459 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 11

Group: 3

Verdict: ACCEPTED

input
`100000 1000 1233 1914 901 3963 1277 4293 1083 1599 ...` view save

correct output
`NO NO YES NO NO ...` view save

user output
`NO NO YES NO NO ...` view save

Test 12

Group: 3

Verdict: ACCEPTED

input
`100000 1000 1970 8631 4606 5797 6317 8162 8204 8789 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` view save

Test 13

Group: 3

Verdict: ACCEPTED

input
`100000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 14

Group: 3

Verdict: ACCEPTED

input
`100000 100000 1 100000 1 100000 1 100000 1 100000 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 15

Group: 3

Verdict: ACCEPTED

input
`100000 100000 80971 98445 93046 96043 74840 94035 95931 96609 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` view save

Test 16

Group: 3

Verdict: ACCEPTED

input
`100000 10000 6481 14350 69129 87600 6217 16462 4387 16625 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Putka Open 2025 – 2/5

Ryhmät

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (Laakeri)