Submission #1267906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267906		Born_To_Laugh	Team Contest (JOI22_team)	C++17	37 / 100	2084 ms	4552 KiB

team

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
const int maxn = 2e5 + 10;
struct Fenwick_Tree
{
    int n;
    vector<int> bit;
    Fenwick_Tree(int len){
        n = len;
        bit.assign(n + 1, -INF);
    }
    void Point_Update(int pos, int val){
        for(; pos<=n; pos += pos & (-pos)){
            bit[pos] = max(bit[pos], val);
        }
    }
    int get(int pos){
        int ans = -INF;
        for(; pos>0; pos -= pos & -pos){
            ans = max(ans, bit[pos]);
        }
        return ans;
    }
};
Fenwick_Tree ft(maxn);
int n;
vector<array<int, 3>> item(maxn);
bool cmp(array<int, 3> a, array<int, 3> b){
    return a[0] < b[0];
}
void solve(){
    cin >> n;
    vector<int> temp;
    for(int i=1; i<=n; ++i){
        cin >> item[i][0] >> item[i][1] >> item[i][2];
        temp.push_back(item[i][1]);
    }
    sort(item.begin() + 1, item.begin() + 1 + n, cmp);
    // for(int i=1; i<=n; ++i){
    //     cout << item[i][0] << ' ' << item[i][1] << ' ' << item[i][2] << '\n';
    // }
    sort(alle(temp));
    temp.erase(unique(alle(temp)), temp.end());
    auto get_pos = [&](int x){
        return upper_bound(alle(temp), x) - temp.begin();
    };
    
    int ans = -INF;
    int id = 1;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<i; ++j){
            if(item[j][0] == item[i][0])break;
            // cout << item[j][0] << ' ' << item[j][1] << '\n';
            if(item[j][1] <= item[i][1])continue;
            int num = ft.get(get_pos(item[j][1]) - 1);
            if(num <= item[j][2] || num <= item[i][2])continue;
            ans = max(ans, item[i][0] + item[j][1] + num);
        }
        if(item[i][0] != item[i + 1][0] && i != 1){
            while(id <= i){
                ft.Point_Update(get_pos(item[id][1]), item[id][2]);
                id++;
            }
        }
    }
    if(ans == -INF)cout << -1 << '\n';
    else cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27