— Dark mode

Putka Open 2025 – 2/5

Ryhmät

  • Start: 2025-09-26 18:00:00
  • End: 2025-09-28 23:00:00
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
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.04 s2details
#7ACCEPTED0.07 s2details
#8ACCEPTED0.29 s2details
#9ACCEPTED0.01 s2, 3details
#10ACCEPTED0.08 s3details
#11ACCEPTED0.08 s3details
#12ACCEPTED0.08 s3details
#13ACCEPTED0.07 s3details
#14ACCEPTED0.22 s3details
#15ACCEPTED0.25 s3details
#16ACCEPTED0.11 s3details

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

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
...
Truncated

Tasks

A Ruudukko-B Leimasin-C Alkuluvut-D Ryhmät-

Submissions (Laakeri)

2025-09-27 12:39:36 100