QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#577136 | #6886. Simple Set Problem | JZYZ# | AC ✓ | 1679ms | 67352kb | C++14 | 1.1kb | 2024-09-20 08:24:30 | 2024-09-20 08:24:30 |
Judging History
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