QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382139#6692. Building Companykevinyang#WA 0ms28764kbC++172.1kb2024-04-08 03:36:462024-04-08 03:36:46

Judging History

你现在查看的是最新测评结果

  • [2024-04-08 03:36:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:28764kb
  • [2024-04-08 03:36:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 300005;
vector<set<pair<int,int>>>tasks(mxn);
vector<int>rem(mxn);
vector<vector<pair<int,int>>>add(mxn);
vector<int>cnt(mxn);

int ans = 0;
queue<pair<int,int>>q;

void modify(int op, int freq){
	cnt[op]+=freq;
	while(tasks[op].size() && (*tasks[op].begin()).first <= cnt[op]){
		pair<int,int>p = *tasks[op].begin();
		tasks[op].erase(p);
		rem[p.second]--;
		if(rem[p.second] == 0){
			ans++;
			for(auto nxt: add[p.second]){
				q.push(nxt);
			}
		}
	}
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int g;
	cin >> g;
	vector<pair<int,int>>arr(g);
	for(int i = 0; i<g; i++){
		int x,y;
		cin >> x >> y;
		arr[i] = {x,y};
	}
	int n;
	cin >> n;
	vector<vector<pair<int,int>>>rq(n+1);
	for(int i = 1; i<=n; i++){
		int m;
		cin >> m;
		for(int j = 0; j<m; j++){
			int x,y;
			cin >> x >> y;
			rq[i].push_back({x,y});
		}
		rem[i] = rq[i].size();
		int k;
		cin >> k;
		for(int j = 0; j<k; j++){
			int x,y;
			cin >> x >> y;
			add[i].push_back({x,y});
		}
	}
	vector<int>sorted;
	for(int i = 0; i<g; i++){
		sorted.push_back(arr[i].first);
	}
	for(int i = 1; i<=n; i++){
		for(auto [a,_] : rq[i]){
			sorted.push_back(a);
		}
		for(auto [a,_] : add[i]){
			sorted.push_back(a);
		}
	}
	sorted.push_back(-5);
	sort(sorted.begin(),sorted.end());
	for(int i = 0; i<g; i++){
		arr[i].first = lower_bound(sorted.begin(),sorted.end(),arr[i].first)-sorted.begin();
	}
	for(int i = 1; i<=n; i++){
		for(int j = 0; j<rq[i].size(); j++){
			rq[i][j].first = lower_bound(sorted.begin(),sorted.end(),rq[i][j].first)-sorted.begin();
			tasks[rq[i][j].first].insert({rq[i][j].second,i});
		}
		for(int j = 0; j<add[i].size(); j++){
			add[i][j].first = lower_bound(sorted.begin(),sorted.end(),add[i][j].first)-sorted.begin();
		}
		if(rem[i] == 0){
			for(auto nxt: add[i]){
				q.push(nxt);
				ans++;
			}
		}
	}
	for(int i = 0; i<g; i++){
		q.push(arr[i]);
	}
	while(q.size()){
		auto [op,freq] = q.front(); q.pop();
		modify(op,freq);
	}
	cout << ans << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 28708kb

input:

2 2 1 1 2
5
1 3 1
0
2 1 1 2 1
2 3 2 2 1
3 1 5 2 3 3 4
1 2 5
3 2 1 1 1 3 4
1 1 3
0
1 3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 28764kb

input:

3 610031727 590328742 816793299 18485566 654221125 47823436
10
3 610031727 224714165 816793299 491951703 654221125 593479446
1 610031727 538596643
1 610031727 551036304
3 816793299 262985484 610031727 52580932 654221125 424397787
1 654221125 889197190
3 654221125 126924193 610031727 963399336 816793...

output:

11

result:

wrong answer 1st numbers differ - expected: '10', found: '11'