QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#577136#6886. Simple Set ProblemJZYZ#AC ✓1679ms67352kbC++141.1kb2024-09-20 08:24:302024-09-20 08:24:30

Judging History

This is the latest submission verdict.

  • [2024-09-20 08:24:30]
  • Judged
  • Verdict: AC
  • Time: 1679ms
  • Memory: 67352kb
  • [2024-09-20 08:24:30]
  • Submitted

answer

#include<bits/stdc++.h>
#define MP make_pair
using namespace std;
typedef pair< int, int > PII;
const int N = 1e6 + 10;
int T, n, c[N], tot;
int lst[N];
struct num {
	int x, col;
}nn[4 * N];
bool cmp(num a, num b) {
	return a.x < b.x;
}
set< PII > s;
int main() {
	scanf("%d", &T);
	while(T -- ) {
		tot = 0;
		scanf("%d", &n); 
		for(int i = 1; i <= n; i ++ ) {
			scanf("%d", &c[i]);
			for(int j = 1; j <= c[i]; j ++ ) {
				int x; scanf("%d", &x);
				nn[++ tot] = (num) {x, i};
			}
		}
		sort(nn + 1, nn + tot + 1, cmp);
		s.clear();
		int res = 2e9 + 10;
		for(int i = 1; i <= n; i ++ ) s.insert(MP(0, i)), lst[i] = 0;
        for(int i = 1; i <= tot; i ++ ) {
            s.erase(MP(lst[nn[i].col], nn[i].col));
            lst[nn[i].col] = i; s.insert(MP(i, nn[i].col));
            auto it = s.begin();
            int pp = (it->first);
            if(!pp) continue;
            res = min(res, nn[i].x - nn[pp].x);
		}
		printf("%d\n", res);
	}
	return 0;
}
/*
3
2
1 6
3 -7 7 10
4
9 -5 -9 2 8 5 4 3 3 8
2 10 8
1 -7
3 1 6 10
1
1 9
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1679ms
memory: 67352kb

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