QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#143269	#5526. Jewel of Data Structure Problems	forelax	TL	2ms	3688kb	C++14	2.0kb	2023-08-21 00:28:03	2023-08-21 00:28:05

Judging History

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

[2023-08-21 00:28:05]
评测

测评结果：TL
用时：2ms
内存：3688kb

查看

[2023-08-21 00:28:03]
提交

answer

#include <bits/stdc++.h>
using namespace std;
vector<int> fwc(200010, 0);
void add(int x)
{
    for (int i = x + 1; i < fwc.size(); i += i & -i)
        fwc[i]++;
}
int cnt(int x)
{
    int res = 0;
    for (int i = x + 1; i > 0; i -= i & -i)
        res += fwc[i];
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    int count_odd = 0;
    int count_right = 0;
    int count_sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        v[i]--;
        count_odd += ((i - v[i]) % 2 != 0);
        count_right += v[i] == i;
        // cout << ((i - v[i]) % 2 != 0) << " ";
    }
    // cout << endl;
    // cout << count_odd << endl;
    for (int i = 0; i < n; i++)
    {
        count_sum += i - cnt(v[i]);
        add(v[i]);
    }
    count_sum &= 1;
    for (int i = 0, a, b; i < q; i++)
    {
        cin >> a >> b;
        // cout << a << " " << b << "    ";
        a--;
        b--;
        count_odd -= ((a - v[a]) % 2 != 0);
        count_odd -= ((b - v[b]) % 2 != 0);
        count_right -= (a == v[a]);
        count_right -= (b == v[b]);
        // cout << ((a - v[a]) % 2 != 0) << " " << ((b - v[b]) % 2 != 0) << "    ";
        swap(v[a], v[b]);
        // cout << ((a - v[a]) % 2 != 0) << " " << ((b - v[b]) % 2 != 0) << "    ";
        count_odd += ((a - v[a]) % 2 != 0);
        count_odd += ((b - v[b]) % 2 != 0);
        count_right += (a == v[a]);
        count_right += (b == v[b]);
        count_sum ^= 1;
// if (count_right == n)
//     cout << -1 << endl;
// else if (count_odd == 0)
//     cout << n - 2 << endl;
// else if (count_sum)
//     cout << n << endl;
// else
//     cout << n - 1 << endl;
#define endl '\n'
        if (count_sum)
            cout << n << endl;
        else if (count_odd)
            cout << n - 1 << endl;
        else if (count_right == n)
            cout << -1 << endl;
        else
            cout << n - 2 << endl;
    }
}
// 41325 14325

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 3688kb

input:

output:

result:

ok 6 numbers

Test #2:

score: -100

Time Limit Exceeded

input:

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
...