QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #136687 | #238. Distinct Values | Vengeful_Spirit# | 100 ✓ | 276ms | 9392kb | C++20 | 1.4kb | 2023-08-09 10:05:57 | 2023-08-09 10:05:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
struct node {
int l, r;
} a[N];
bool cmp(node A, node B) {
return (A.l == B.l) ? A.r > B.r : A.l < B.l;
}
int ans[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while(T--) {
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
cin >> a[i].l >> a[i].r;
}
sort(a + 1, a + 1 + m, cmp);
set<int> s;
for(int i = 1; i <= n; ++i) s.insert(i);
int L = 1, R = 0;
for(int o = 1; o <= m; ++o) {
auto[l, r] = a[o];
if(r <= R) continue;
if(l > R) {
for(int i = L; i <= R; ++i) s.insert(ans[i]);
for(int i = R + 1; i < l; ++i) ans[i] = 1;
for(int i = l; i <= r; ++i) {
int x = *s.begin();
ans[i] = x;
s.erase(x);
}
} else {
for(int i = L; i < l; ++i) s.insert(ans[i]);
for(int i = R + 1; i <= r; ++i) {
int x = *s.begin();
ans[i] = x;
s.erase(x);
}
}
L = l, R = r;
}
for(int i = R + 1; i <= n; ++i) ans[i] = 1;
for(int i = 1; i <= n; ++i) cout << ans[i] << " ";
cout << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 276ms
memory: 9392kb
input:
11116 10 2 5 5 5 6 10 1 7 10 10 1 2 6 10 1 2 5 10 1 6 7 10 2 8 9 7 10 10 2 1 4 6 10 10 4 8 8 10 10 3 6 1 5 10 3 8 8 10 10 8 10 10 4 6 10 1 5 2 6 1 2 10 3 4 4 4 8 4 8 10 4 1 5 1 2 5 5 2 4 10 4 2 5 9 10 6 7 2 4 10 1 5 6 10 4 10 10 8 10 2 5 10 10 10 1 1 2 10 4 7 8 5 6 7 9 10 10 10 4 3 7 6 6 8 10 3 4 10...
output:
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 3 4 1 1 2 3 4 5 1 1 1 1 1 1 2 3 4 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 3 4 1 2 3 4 1 1 2 3 4 5 1 2 3 4 5 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 1 2 3 4 5 1 2 3 4 5 1 1 1 1 2 3 4 5 1 1 1 2 3 4 5 1 1 1 1 1 1 1 2 3 4 1 2 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 ...
result:
ok 11116 lines