QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#809767#9786. Magical BagsAfterlife#WA 1ms3852kbC++201.5kb2024-12-11 17:14:472024-12-11 17:14:48

Judging History

你现在查看的是最新测评结果

  • [2024-12-11 17:14:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3852kb
  • [2024-12-11 17:14:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+1e3+7;

int n;

vector<int> L,R,v[N];

int qry(vector<int> &a,int l,int r)
{
    if(l>r)
        return 0;
    return upper_bound(a.begin(),a.end(),r)-lower_bound(a.begin(),a.end(),l);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        v[i].resize(k);
        for(auto &x:v[i])
            cin>>x;
        L.push_back(*min_element(v[i].begin(),v[i].end()));
        R.push_back(*max_element(v[i].begin(),v[i].end()));
    }
    sort(L.begin(),L.end());
    sort(R.begin(),R.end());
    vector<pair<int,int> >segs;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        sort(v[i].begin(),v[i].end());
        int ok=0;
        for(auto x:v[i])
        {
            int bad=0;
            {
                int s=v[i][0]+1,t=x;
                if(qry(R,s,t))
                    bad=1;
            }
            {
                int s=x,t=v[i].back()-1;
                if(qry(L,s,t))
                    bad=1;
            }
            ok|=!bad;
        }
        ans+=2;
        if(ok)
            segs.push_back({v[i].front(),v[i].back()});
    }
    sort(segs.begin(),segs.end(),[&](const auto &a,const auto &b) {
        return a.second<b.second;
    });
    int rp=-10;
    for(auto [l,r]:segs)
    {
        if(l<rp)
            continue;
        rp=r;
        ans--;
    }
    cout<<ans<<"\n";
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3852kb

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: 1ms
memory: 3572kb

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3508kb

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: 1ms
memory: 3656kb

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3564kb

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:

179

result:

wrong answer 1st numbers differ - expected: '177', found: '179'