QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#782867 | #9786. Magical Bags | daduoli | WA | 4ms | 28536kb | C++14 | 1.4kb | 2024-11-25 21:55:17 | 2024-11-25 21:55:19 |
Judging History
answer
#include<bits/stdc++.h>
#define Yzl unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define lob lower_bound
#define upb upper_bound
#define pb emplace_back
typedef long long LL;
using namespace std;
const Yzl Lty=20120712;
const int MAXN=5e5+10;
int n;
int len[MAXN],tot,lsh[MAXN],L[MAXN],R[MAXN],l[MAXN],r[MAXN];
vector<int> e[MAXN];
struct itv {
int l,r;
}ind[MAXN]; int cnt,tp;
int main () {
scanf("%d",&n); int ans=0;
for(int i=1;i<=n;++i) {
scanf("%d",&len[i]); for(int j=1;j<=len[i];++j) { int x; scanf("%d",&x); e[i].pb(x); lsh[++tot]=x; }
} sort(lsh+1,lsh+1+tot); tot=unique(lsh+1,lsh+1+tot)-lsh-1;
for(int i=1;i<=n;++i) for(int j=0;j<len[i];++j) e[i][j]=lob(lsh+1,lsh+1+tot,e[i][j])-lsh;
for(int i=1;i<=n;++i) { if(len[i]==1) { ++ans; continue; }
sort(e[i].begin(),e[i].end()); ans+=2;
l[++tp]=e[i][0]; r[++tp]=e[i][len[i]-1];
} sort(l+1,l+1+tp); sort(r+1,r+1+tp); r[tp+1]=Lty;
for(int i=1;i<=n;++i) { if(len[i]==1) continue;
L[i]=l[upb(l+1,l+1+tp,e[i][len[i]-1])-l-1];
R[i]=r[lob(r+1,r+1+tp,e[i][0])-r];
bool sf=0;
for(int j=0;j<len[i];++j) {
if(e[i][j]<=R[i]&&e[i][j]>=L[i]) sf=1;
}
if(sf) ind[++cnt]=(itv){e[i][0],e[i][len[i]-1]};
} sort(ind+1,ind+1+cnt,[&](itv a,itv b){return a.l<b.l;});
int lt=0;
for(int i=1;i<=cnt;++i) {
if(ind[i].l>lt) lt=ind[i].r,--ans;
else lt=min(lt,ind[i].r);
} printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 26360kb
input:
4 3 4 7 10 2 1 9 4 11 2 8 14 3 6 12 13
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 4ms
memory: 22212kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 4ms
memory: 26424kb
input:
4 3 4 7 10 2 1 9 4 11 2 8 14 3 6 12 13
output:
7
result:
ok 1 number(s): "7"
Test #4:
score: 0
Accepted
time: 0ms
memory: 20292kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 4ms
memory: 28536kb
input:
100 4 372861091 407948190 424244630 359746969 6 568180757 527358812 494745349 665803213 674832670 586694351 4 696340797 775899164 919971335 716827187 4 123145962 344250363 122030550 251739234 4 342654413 368648894 150539766 255189030 1 194505887 3 755984448 736803561 745474041 4 709314938 498953418 ...
output:
177
result:
ok 1 number(s): "177"
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 28508kb
input:
100 5 128474911 128789041 128389100 128571722 128449204 4 190783009 179144907 191954599 169739385 7 922968028 923017780 923012667 922993373 923012653 923010830 922983606 1 399117777 8 693609160 693615962 692956804 692902832 694104582 693605539 693750551 692909362 4 133590022 156691169 120354087 1477...
output:
172
result:
wrong answer 1st numbers differ - expected: '175', found: '172'