QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#196396#6886. Simple Set ProblemRoyo#AC ✓1228ms58556kbC++201.8kb2023-10-01 16:49:492023-10-01 16:49:50

Judging History

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

  • [2023-10-01 16:49:50]
  • 评测
  • 测评结果:AC
  • 用时:1228ms
  • 内存:58556kb
  • [2023-10-01 16:49:49]
  • 提交

answer

#include <bits/stdc++.h>
#include <cstdio>
//#define int long long
#define PII pair<int, int>
#pragma GCC optimize("Ofast")
#define NO {puts("No") ; return ;}
#define YES {puts("Yes") ; return ;}
#define pb push_back
#define endl "\n"
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
mt19937 rd(time(0));
const int N = 1e5 + 10;

void solve() {
	int n; cin >> n;
	vector<PII> v;
	for (int i = 1; i <= n; i++)
	{
		int k; cin >> k;
		for (int j = 1; j <= k; j++)
		{
			int x; cin >> x;
			v.pb({x, i});
		}
	}
	//exit(0);
	sort(v.begin(), v.end());
	
	//for (auto it : v) cout << it.fi << ' ' << it.se << endl;
	
	if (n == 1)
	{
		cout << 0 << endl;
		return;
	}
	map<int, int> q;
	int kind = 0;
	int ans = 1e17;
	//cout << endl;
	int r = 0;
	int ma = 0;
	for (int l = 0; l < v.size() - n + 1; l++)
	{
		int c = v[l].fi, ver = v[l].se;
		if (kind == n) 
		{
			//cout << ver << ' ' << ver1 << endl;
			//cout << c << ' ' << ma << endl;
			ans = min(ma - c, ans);
		}
		while (kind != n && r < v.size())
		{
			int c1 = v[r].fi, ver1 = v[r].se;
			if (q[ver1] != 0) q[ver1]++, r++;
			else
			{
				q[ver1]++; kind++;
				r++;
				ma = c1;
			}
			if (kind == n) 
			{
				//cout << ver << ' ' << ver1 << endl;
				//cout << c << ' ' << ma << endl;
				ans = min(ma - c, ans);
				break;
			}
		}
		
		//cout << q[3] << endl;
		// q[ver]++;
		// if (q[ver] == 1) kind++;
		
		//if (kind == n) ans = min(ma - c, ans);
		
		q[ver]--;
		//if (ver == 3) cout << q[ver] << "!!!!" << endl;
		if (q[ver] == 0) kind--;
		
	}
	cout << ans << endl;
} 

signed main() {
    IOS;
    int t; cin >> t;
    while (t -- ) 
    solve();
    
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1228ms
memory: 58556kb

input:

10018
1
5 -247462786 -97914904 849160785 -951926514 -829935728
7
72 8382969 -3251289 -63130380 -590108505 -798189380 -140833313 -626464256 136468139 -711222365 500861930 -459837972 914918723 186793042 872925162 -335485808 641571163 -314777234 -520573290 -894124702 618889116 2700292 -714868427 -34346...

output:

0
1800402714
860165806
487641037
229279918
238532335
392707612
456994871
256099628
1023121975
4986247
753213024
0
1289600751
598093746
55025093
95257568
145430738
34342513
0
157895624
789721360
232287715
1817496622
439049782
777966568
29118927
1671939338
1048279188
42073227
642353647
61747459
302989...

result:

ok 10018 lines