QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#93510#6136. AirdroplamWA 617ms14232kbC++143.0kb2023-04-01 07:53:032023-04-01 07:53:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-01 07:53:05]
  • 评测
  • 测评结果:WA
  • 用时:617ms
  • 内存:14232kb
  • [2023-04-01 07:53:03]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
int n,Y,m;
vector <int> d;
int pre[maxn],suf[maxn];
ii a[maxn];
map<int,bool> mp;
bool cmp(ii x, ii y)
{
    return x.ff>y.ff;
}
void xuly()
{
    cin>>n>>Y;
    for (int i=1; i<=n; i++) cin>>a[i].ff>>a[i].ss,d.push_back(a[i].ff);
    int it=1;
    sort(d.begin(),d.end());
    d.resize(unique(d.begin(),d.end())-d.begin());
    m=d.size();
    sort(a+1,a+n+1);
    mp.clear();
    pre[0] = 0;
    for (int i=1; i<=m; i++)
    {
        pre[i] = pre[i-1];
        vector <int> tmp;
        while (it<=n&&a[it].ff<=d[i-1])
        {
            int val = abs(a[it].ss-Y) - a[it].ff;
            tmp.push_back(val);

            it++;
        }
        int l,r;
        sort(tmp.begin(),tmp.end());
        for (int j=0; j<tmp.size(); j++)
        {
            if (j==0||tmp[j]!=tmp[j-1]) l=j;
            if (j==tmp.size()+1||tmp[j]!=tmp[j+1])
            {
                r=j;
                int val = tmp[j];
                if (mp.count(val))
                {
                    mp[val]=0;
                    pre[i]-=(r-l+2);
                }
                else if (r-l+1>1)
                {
                    pre[i]-=(r-l+1);
                }
                else mp[val]=1;
            }
        }
    }
    sort(a+1,a+n+1,cmp);
    mp.clear();
    suf[m+1] = 0;
    it=1;
    for (int i=m; i>=1; i--)
    {
        suf[i]=suf[i+1];
        vector <int> tmp;
        while (it<=n&&a[it].ff>=d[i-1])
        {
            int val = abs(a[it].ss-Y) + a[it].ff;
            tmp.push_back(val);

            it++;
        }
        int l,r;
        sort(tmp.begin(),tmp.end());
        for (int j=0; j<tmp.size(); j++)
        {
            if (j==0||tmp[j]!=tmp[j-1]) l=j;
            if (j==tmp.size()+1||tmp[j]!=tmp[j+1])
            {
                r=j;
                int val = tmp[j];
//                cout<<i<<' '<<r-l+1<<' '<<val<<'\n';
                if (mp.count(val))
                {
                    mp[val]=0;
                    suf[i]-=(r-l+2);
                }
                else if (r-l+1>1)
                {
                    suf[i]-=(r-l+1);
                }
                else mp[val]=1;
            }
        }
    }
    int mmax = max(pre[m]+n,n+suf[1]); int mmin = min(n+pre[m],n+suf[1]);
//    for (int i=0; i<=m; i++) cout<<pre[i]<<' '; cout<<'\n';
//    for (int i=1; i<=m+1; i++) cout<<suf[i]<<' '; cout<<'\n';
    for (int i=1; i<=m; i++)
    {
        mmax = max(mmax,n+pre[i-1]+suf[i+1]);
        mmin = min(mmin,n+pre[i-1]+suf[i+1]);
        if (i>1&&abs(d[i-1]-d[i-2])>1)
        {
            mmax = max(mmax,n+pre[i-1]+suf[i]);
            mmin = min(mmin,n+pre[i-1]+suf[i]);
        }
    }
    cout<<mmin<<' '<<mmax<<'\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int tt; cin>>tt;
    while (tt--) xuly();
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 5464kb

input:

3
3 2
1 2
2 1
3 5
3 3
2 1
2 5
4 3
2 3
1 3
4 3

output:

1 3
0 3
2 2

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 617ms
memory: 14232kb

input:

3508
6 1
7 1
1 1
9 1
10 1
3 1
4 1
3 8
8 9
8 7
1 8
9 5
10 1
10 8
10 2
5 1
9 9
5 9
10 9
6 4
4 7
6 7
10 5
3 8
9 5
9 9
7 5
4 7
10 5
6 9
9 5
6 6
9 3
3 2
5 1
3 8
6 4
5 9
10 2
2 9
10 10
10 8
4 1
7 1
6 1
3 1
5 1
2 4
9 3
3 3
4 5
3 8
9 6
9 9
6 3
9 5
9 3
2 9
9 1
9 2
4 1
5 4
5 6
6 5
9 8
4 1
2 1
5 1
7 1
3 1
9 10...

output:

6 6
1 3
1 5
2 6
3 8
0 2
4 4
2 2
4 4
2 7
4 4
9 9
4 6
0 5
2 6
2 2
2 6
10 10
9 9
1 3
2 4
0 2
2 4
4 7
6 6
9 9
2 2
2 2
3 5
1 4
2 2
1 1
3 5
4 9
3 6
1 1
5 7
5 5
1 3
2 2
1 7
1 1
4 6
2 4
2 6
2 4
1 7
2 4
9 9
0 3
1 1
3 8
2 2
2 2
9 9
3 7
4 4
4 6
2 5
0 2
2 5
3 3
0 4
4 4
2 4
2 2
6 8
6 6
6 6
0 2
2 6
2 4
2 6
2 5
1 ...

result:

wrong answer 9th numbers differ - expected: '2', found: '3'