QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #30354 | #238. Distinct Values | srf | AC ✓ | 327ms | 9440kb | C++ | 908b | 2022-04-27 14:41:54 | 2022-04-28 16:58:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
inline void read(int &x){
static char c; x = 0,c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + c - '0',c = getchar();
}
int n;
int l[100005];
int ans[100005],cnt[100005];
set<int>S;
void solve(){
int i,q,ql,qr;
read(n),read(q);
S.clear();
for (i = 1; i <= n; ++i) cnt[i] = ans[i] = 0,l[i] = i,S.insert(i);
while (q--) read(ql),read(qr),l[qr] = min(l[qr],ql);
for (i = n-1; i ; --i) l[i] = min(l[i],l[i+1]);
ans[1] = 1,++cnt[1]; if (cnt[1] == 1) S.erase(1);
for (i = 2; i <= n; ++i){
for (int j = l[i-1]; j < l[i]; ++j){
--cnt[ans[j]];
if (cnt[ans[j]] == 0) S.insert(ans[j]);
}
ans[i] = *S.begin();
++cnt[ans[i]],S.erase(ans[i]);
}
for (i = 1; i <= n; ++i) cout << ans[i] << (i<n?' ':'\n');
}
int main(){
int T; read(T);
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 327ms
memory: 9440kb
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 3 4 1 1 1 2 3 ...
result:
ok 11116 lines