Submission #1170735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170735		tw20000807	Team Contest (JOI22_team)	C++20	0 / 100	172 ms	46148 KiB

team

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;
const int maxn = 1.5e5 + 10;
const int mod = 1e9 + 7;//    998244353;
const int llmx = 1e18;

array<int, 3> v[maxn];
int n;
struct TREE{
    vector< array<int, 2> > a, b, sa, sb;
    vector< int > ans;
    TREE(int N){
        n = N;
        a.resize(4 * n + 10);
        b.resize(4 * n + 10);
        sa.resize(4 * n + 10);
        sb.resize(4 * n + 10);
        ans.resize(4 * n + 10);
    }
    void pull(int id){
        a[id] = max(a[id << 1], a[id << 1 | 1]);
        b[id] = max(b[id << 1], b[id << 1 | 1]);
        for(auto &t : {a[id << 1], a[id << 1 | 1], sa[id << 1], sa[id << 1 | 1]}) if(a[id] != t){
            sa[id] = t;
        }
        for(auto &t : {b[id << 1], b[id << 1 | 1], sb[id << 1], sb[id << 1 | 1]}) if(b[id] != t){
            sb[id] = t;
        }
        ans[id] = max(ans[id << 1], ans[id << 1 | 1]);
        for(auto &l : {a[id], sa[id]}) for(auto &r : {b[id], sb[id]}){
            if(l[0] != -r[1] && r[0] != -l[1])ans[id] = max(ans[id], l[0] + r[0]);
        }
    }
    void build(int id = 1, int l = 0, int r = n - 1){
        if(l == r){
            a[id] = {v[l][1], -v[l][2]};
            b[id] = {v[l][2], -v[l][1]};
            sa[id] = {-llmx, -llmx};
            sb[id] = {-llmx, -llmx};
            ans[id] = -llmx;
            return ;
        }
        else{
            int mid = (l + r) >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            pull(id);
        }
    }
    void modify(int qx, int id = 1, int l = 0, int r = n - 1){
        if(l == r){
            a[id] = b[id] = sa[id] = sb[id] = {-llmx, -llmx};
            ans[id] = -llmx;
            return;
        }
        int mid = (l + r) >> 1;
        if(qx <= mid) modify(qx, id << 1, l, mid);
        else modify(qx, id << 1 | 1, mid + 1, r);
        pull(id);
    }
    int query(){
        return ans[1];
    }
};
void sol(){
    int n; cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> v[i][0] >> v[i][1] >> v[i][2];
    }
    sort(v, v + n, greater<>());
    TREE tree(n);
    tree.build();
    int ans = -1;
    // for(int i = 0; i < n; ++i) cerr << v[i][0] << " " << v[i][1] << " " << v[i][2] << "!!\n";
    for(int i = 0, j = 0; i < n; i = j){
        while(j < n && v[i][0] == v[j][0]){
            tree.modify(j);
            ++j;
        }
        ans = max(ans, v[i][0] + tree.query());
    }
    cout << ans << "\n";
}
/*

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

// 13
8
1 1 1
1 1 5
1 5 1
5 1 1
1 5 5
5 1 5
5 5 1
5 5 5

// 15

4
1 2 3
1 2 3
1 2 3
1 2 3
// -1

*/
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
    int t = 1; //cin >> t;
    while(t--) sol();
}

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