Submission #1176232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176232		nguyenkhangninh99	Team Contest (JOI22_team)	C++17	100 / 100	95 ms	4788 KiB

team

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;

array<int, 3> a[maxn];
vector<int> ys, zs;

struct FenwickTree{
    int tree[maxn];

    void update(int id, int val){
        for(; id < maxn; id += id & (-id)) tree[id] = max(tree[id], val);
    }

    int get(int id){
        int res = 0;
        for(; id; id -= id & (-id)) res = max(res, tree[id]);
        return res;
    }
} bity, bitz;

void solve(){
    int n; cin >> n;

    for(int i = 1; i <= n; i++){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        ys.push_back(a[i][1]);
        zs.push_back(a[i][2]);
    }

    sort(ys.begin(), ys.end());
    sort(zs.begin(), zs.end());

    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    zs.erase(unique(zs.begin(), zs.end()), zs.end());

    for(int i = 1; i <= n; i++){
        a[i][1] = lower_bound(ys.begin(), ys.end(), a[i][1]) - ys.begin() + 1;
        a[i][2] = lower_bound(zs.begin(), zs.end(), a[i][2]) - zs.begin() + 1;
    }

    sort(a + 1, a + n + 1);

    int res = 0, y = 0, z = 0, j = 1;
    for(int i = 1; i <= n; i++){
        if (a[i][0] != a[i - 1][0]){
            for (int k = j; k < i; k++){
                int tmpz = bity.get(a[k][1] - 1), tmpy = bitz.get(a[k][2] - 1);
                //tmpz lớn nhất bé hơn a[k][1];
                //tmpy lớn nhất bé hơn a[k][2];
                //nếu tmpz lớn hơn a[k][2], và tmpz >= z và a[k][1] >= y;

                if (tmpz > a[k][2] && tmpz + a[k][1] >= y + z){
                    y = a[k][1];
                    z = tmpz;
                }

                if (tmpy > a[k][1] && tmpy + a[k][2] >= y + z){
                    y = tmpy;
                    z = a[k][2];
                }
                bity.update(a[k][1], a[k][2]);
                bitz.update(a[k][2], a[k][1]);
            }

            j = i;
        }

        if (y > a[i][1] && z > a[i][2]) res = max(res, a[i][0] + ys[y - 1] + zs[z - 1]);
    }

    cout << (res ? res : -1);
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	solve();
}

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