QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#671471#6695. MatchingSchoolbagRE 0ms3536kbC++202.3kb2024-10-24 12:43:422024-10-24 12:43:43

Judging History

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

  • [2024-10-24 12:43:43]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3536kb
  • [2024-10-24 12:43:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vc;
typedef vector<long long> vl;
typedef vector<vector<long long>> vll;
typedef __int128_t int128;
#define rep(x, y, z) for(int x = (y); x <= (z); x++)
#define per(x, y ,z) for(int x = (y); x >= (z); x--)
#define yes cout << "Yes\n"
#define no cout << "No\n"

//#define int long long
//const int N = 1e5 + 5;
//const int mod = 1e9 + 7;
const int inf = -1e9 - 5;

struct dsu{
    vi fa, siz;
    void init(int n){ // 初始化
        fa.resize(n + 1);
        iota(fa.begin(), fa.end(), 0);
        siz.resize(n + 1, 1);
    }
    int find(int x){
        if(x == fa[x]) return x;
        return fa[x] = find(fa[x]);
    }
    void merge(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return;
        if(siz[x] > siz[y]) swap(x, y);
        fa[x] = y, siz[y] += siz[x];
        return;
    }
}d;
void solve(){
    int n; cin >> n;
    d.init(n);
    vector<pii> p(n + 1, {-1, -1});
    rep(i, 1, n){
        cin >> p[i].first;
        p[i].second = p[i].first - i;
    }
    sort(p.begin() + 1, p.end(), [&](pii x, pii y){
        return x.second < y.second;
    });
    rep(i, 1, n){
        int r = i;
        while(p[i].second == p[r].second) r++;
        r--;
        rep(j, i, r){
            d.merge(i, j);
        }
        i = r;
    }
    map<int, vi> mp;
    rep(i, 1, n){
        int fa = d.find(i);
        mp[fa].push_back(p[i].first);
    }
    ll ans = 0;
    for(auto [x, y] : mp){
        sort(y.begin(), y.end(), [&](int x, int y){
            return x > y;
        });
        int leny = y.size();
        for(int i = 0; i < leny; i += 2){
            if(i + 1 < leny){
                if(y[i] + y[i+1] > 0){
                    ans += y[i] + y[i+1];
                }
                else break;
            }
        }
    }
    cout << ans << '\n';
}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int __ = 1; cin >> __;
    while(__--){
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3536kb

input:

3
9
3 -5 5 6 7 -1 9 1 2
3
-5 -4 -3
3
1 10 100

output:

30
0
0

result:

ok 3 number(s): "30 0 0"

Test #2:

score: -100
Runtime Error

input:

5504
9
-1 -7 -6 -5 -4 -3 5 -1 0
5
999999995 999999993 999999995 999999995 999999995
5
3 -6 -5 -4 -2
4
-8 2 3 -5
4
-2 -1 0 1
9
-4 -9 3 -1 -1 -5 2 -3 -5
7
-1 -2 1 2 3 4 3
4
-2 5 2 -4
10
2 4 1 -3 -2 4 5 -3 0 -4
6
-1 0 1 2 4 -3
5
-4 -3 -2 -1 0
4
-1 0 1 2
8
1 0 -4 -1 0 -5 -3 -5
2
5 6
8
-4 -3 -2 -1 0 1 2 ...

output:


result: