QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243845#5526. Jewel of Data Structure ProblemsGeospizaWA 28ms5960kbC++203.4kb2023-11-08 18:04:562023-11-08 18:04:56

Judging History

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

  • [2023-11-08 18:04:56]
  • 评测
  • 测评结果：WA
  • 用时：28ms
  • 内存：5960kb
查看
  • [2023-11-08 18:04:56]
  • 提交

answer

//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define Ma 1000005
#define G 3
#define pb push_back
#define L (1<<21)
#define all(x) x.begin(),x.end()
using namespace std;
ll n,m;
ll a[Ma],b[Ma];
ll ans=0;
ll f[Ma];
ll cnt=0,cnt2=0,cnt3=0;

void merage(ll l,ll r)
{
    if (l==r)
        return ;
    ll mid=(l+r)>>1;
    merage(l,mid),merage(mid+1,r);
    ll i=l,j=mid+1,k=0;
    while (i<=mid&&j<=r){
        if (a[i]<=a[j]) b[k++]=a[i++];
        else ans+=mid-i+1,b[k++]=a[j++];
    }
    while (j<=r) b[k++]=a[j++];
    while (i<=mid) b[k++]=a[i++];
    for (ll k=0;k<r-l+1;k++)
        a[l+k]=b[k];
    return;
}

void add(ll x,ll id)
{
    f[id]=x;
    if (f[id]==id) cnt++;
    if (id==1&&(n&1))
        cnt2+=(f[id]==1);
    else
    {
        ll ch=(n+id)&1;
        if (ch)
        {
            if (f[id+1]==f[id]+1)
                cnt2++;
        }
        else
        {
            if (f[id-1]==f[id]-1)
                cnt2++;
        }
    }
    if (id==1&&(n&1))
        cnt3+=(f[id]==n);
    else
    {
        ll ch=(n+id)&1;
        if (ch)
        {
            if (f[id+1]==f[id]-1)
                cnt3++;
        }
        else
        {
            if (f[id-1]==f[id]+1)
                cnt3++;
        }
    }
}

void del(ll x,ll id)
{
    if (f[id]==id) cnt--;
    if (id==1&&(n&1))
        cnt2-=(f[id]==1);
    else
    {
        ll ch=(n+id)&1;
        if (ch)
        {
            if (f[id+1]==f[id]+1)
                cnt2--;
        }
        else
        {
            if (f[id-1]==f[id]-1)
                cnt2--;
        }
    }
    if (id==1&&(n&1))
        cnt3-=(f[id]==n);
    else
    {
        ll ch=(n+id)&1;
        if (ch)
        {
            if (f[id+1]==f[id]-1)
                cnt3--;
        }
        else
        {
            if (f[id-1]==f[id]+1)
                cnt3--;
        }
    }
    f[id]=-1;
}

void sol()
{
    cin>>n>>m;
    for (ll i=1;i<=n;i++)
        cin>>a[i],f[i]=a[i];
    for (ll i=1;i<=n;i++)
        cnt+=(i==f[i]);
    if (n&1)
    {
        cnt2+=(f[1]==1);
        cnt3+=(f[1]==n);
        for (ll i=2;i<=n;i+=2)
            cnt2+=(f[i+1]-f[i]==1);
        for (ll i=2;i<=n;i+=2)
            cnt3+=(f[i+1]-f[i]==-1);
    }
    else
    {
        for (ll i=1;i<=n;i+=2)
            cnt2+=(f[i+1]-f[i]==1);
        for (ll i=1;i<=n;i+=2)
            cnt3+=(f[i+1]-f[i]==-1);
    }
    merage(1,n);
    ll ca=0;
    for (ll i=1;i<=m;i++)
    {
        ll x,y;
        cin>>x>>y;
        ll px=f[x],py=f[y];
        del(px,x),del(py,y);
        add(py,x),add(px,y);
       // printf("cnt=%lld\n",cnt);
        if (n==1)
            printf("-1\n");
        else if (n==2)
        {
            if ((ans+i)&1)
                printf("%lld\n",n);
            else
                printf("-1\n");
        }
        else if (cnt==n)
            printf("-1\n");
        else if ((ans+i)&1)
            printf("%lld\n",n);
        else if (cnt2==(n+1)/2||((n&1)&&cnt3==(n+1)/2))
            printf("%lld\n",n-2);
        else
            printf("%lld\n",n-1);
    }
}

int	main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll tt=1;
    //cin>>tt;
   while (tt--)
        sol();
    return 0;
}
/*500000 500000*/
源文件, 语言: C++20

详细

Test #1:

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

input:

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

output:

-1
5
4
5
3
5

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 22ms
memory: 5868kb

input:

2 200000
1 2
2 1
2 1
2 1
1 2
1 2
2 1
1 2
2 1
2 1
1 2
2 1
2 1
2 1
2 1
2 1
2 1
1 2
2 1
2 1
1 2
1 2
2 1
1 2
1 2
1 2
1 2
2 1
1 2
1 2
1 2
2 1
2 1
1 2
2 1
2 1
2 1
2 1
1 2
1 2
2 1
2 1
1 2
2 1
1 2
1 2
2 1
1 2
1 2
2 1
2 1
1 2
1 2
2 1
2 1
2 1
1 2
1 2
1 2
1 2
2 1
1 2
2 1
1 2
1 2
2 1
1 2
2 1
1 2
2 1
2 1
2 1
2 1...

output:

2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
...

result:

ok 200000 numbers

Test #3:

score: 0
Accepted
time: 24ms
memory: 5900kb

input:

3 200000
2 1 3
2 1
1 3
2 3
2 3
1 3
2 1
2 1
1 3
1 2
3 1
3 1
2 1
1 2
2 1
2 3
2 1
1 3
1 2
1 2
2 3
1 2
2 1
3 2
3 2
1 3
3 2
1 3
2 1
2 1
3 2
2 1
1 3
1 2
1 2
3 1
2 3
2 1
3 2
3 1
1 2
1 2
2 3
1 2
1 2
3 2
3 1
1 2
3 1
1 2
1 3
1 2
2 3
2 3
3 2
2 1
1 3
2 1
3 1
2 1
3 1
3 1
2 3
1 3
2 1
3 2
2 1
3 1
2 3
3 1
2 3
1 3
1...

output:

-1
3
2
3
-1
3
-1
3
2
3
2
3
2
3
2
3
2
3
2
3
-1
3
2
3
2
3
-1
3
-1
3
2
3
-1
3
2
3
2
3
2
3
2
3
2
3
2
3
-1
3
2
3
2
3
2
3
2
3
2
3
-1
3
-1
3
2
3
2
3
2
3
2
3
-1
3
2
3
-1
3
-1
3
-1
3
2
3
-1
3
-1
3
2
3
2
3
2
3
2
3
-1
3
2
3
2
3
2
3
-1
3
-1
3
-1
3
-1
3
2
3
2
3
2
3
2
3
-1
3
-1
3
2
3
-1
3
2
3
2
3
2
3
-1
3
-1
3
2
...

result:

ok 200000 numbers

Test #4:

score: 0
Accepted
time: 28ms
memory: 5960kb

input:

4 200000
3 1 2 4
3 2
1 3
4 2
2 1
4 2
4 2
4 3
1 3
2 1
4 3
3 4
1 3
1 2
1 3
4 3
3 1
2 4
1 4
4 3
2 1
1 3
2 4
4 2
1 3
2 1
3 2
4 1
2 1
1 4
1 3
4 3
1 2
1 4
4 1
1 3
4 2
2 3
3 4
4 2
1 4
3 1
4 1
1 4
4 1
2 3
2 4
1 2
1 2
4 1
3 4
3 4
3 4
3 1
4 3
4 1
4 3
2 3
2 4
4 3
3 2
2 3
4 2
1 2
1 2
1 2
3 2
2 3
4 1
3 4
3 4
2 3...

output:

4
-1
4
3
4
3
4
3
4
-1
4
3
4
3
4
2
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
-1
4
-1
4
2
4
3
4
3
4
2
4
2
4
3
4
3
4
-1
4
-1
4
3
4
-1
4
3
4
3
4
-1
4
-1
4
3
4
3
4
3
4
2
4
2
4
3
4
3
4
-1
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
2
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
3
4
...

result:

ok 200000 numbers

Test #5:

score: -100
Wrong Answer
time: 28ms
memory: 5960kb

input:

5 200000
5 2 4 3 1
3 2
2 5
5 3
4 3
5 4
2 1
4 1
2 4
4 5
2 4
5 1
2 3
1 3
3 4
1 4
2 5
5 4
4 1
3 1
2 3
5 2
1 4
3 4
5 2
4 2
2 3
5 4
1 2
2 4
2 5
4 5
1 2
3 4
1 2
2 1
3 2
3 4
5 2
1 3
4 1
3 1
4 1
5 3
3 5
1 5
1 3
3 4
3 1
2 4
2 4
3 2
3 2
5 2
4 1
4 5
5 1
5 4
1 5
4 5
3 2
3 5
4 1
3 2
3 2
4 3
3 4
2 5
5 1
1 3
4 3
4...

output:

5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
3
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
3
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
3
5
4
5
4
5
4
5
-1
5
4
5
4
5
-1
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
4
5
...

result:

wrong answer 36th numbers differ - expected: '3', found: '4'
English 繁體中文 简体中文

服务器时间: 2024-12-11 23:22:15 | 开源项目