Submission #1208049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208049		Andrey	Team Contest (JOI22_team)	C++20	0 / 100	89 ms	14004 KiB

team

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

vector<int> x(200001);
vector<int> y(200001);
vector<int> z(200001);

vector<int> seg(1000001,INT_MAX);
vector<int> big(1000001,-1);

void upd(int l, int r, int x, int p, int c) {
    if(l == r) {
        seg[x] = c;
        big[x] = c;
        return;
    }
    int mid = (l+r)/2;
    if(p <= mid) {
        upd(l,mid,x*2,p,c);
    }
    else {
        upd(mid+1,r,x*2+1,p,c);
    }
    seg[x] = min(seg[x*2],seg[x*2+1]);
    big[x] = max(big[x*2],big[x*2+1]);
}

int calc1(int l, int r, int x, int d) {
    if(l == r) {
        if(seg[x] < d) {
            return l;
        }
        else {
            return l+1;
        }
    }
    int mid = (l+r)/2;
    if(seg[x*2] < d) {
        return calc1(l,mid,x*2,d);
    }
    else {
        return calc1(mid+1,r,x*2+1,d);
    }
}

int calc2(int l, int r, int x, int d) {
    if(l == r) {
        if(big[x] > d) {
            return l;
        }
        else {
            return l-1;
        }
    }
    int mid = (l+r)/2;
    if(big[x*2+1] > d) {
        return calc2(mid+1,r,x*2+1,d);
    }
    else {
        return calc2(l,mid,x*2,d);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    vector<pair<pair<int,int>,int>> idk(0);
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> z[i];
        idk.push_back({{x[i],y[i]},i});
    }
    sort(idk.begin(),idk.end());
    reverse(idk.begin(),idk.end());
    vector<int> pos(n);
    for(int i = 0; i < n; i++) {
        pos[idk[i].second] = i;
    }
    int ans = -1,mx = -1,my = -1;
    int p = n;
    vector<pair<int,int>> banana(n);
    for(int i = 0; i < n; i++) {
        banana[i] = {z[i],i};
    }
    sort(banana.begin(),banana.end());
    int w = 0;
    vector<bool> yeah(n);
    while(w < n) {
        int r = n-1;
        for(int i = w; i < n; i++) {
            if(banana[i].first != banana[w].first) {
                r = i-1;
                break;
            }
        }
        for(int i = w; i <= r; i++) {
            int c = banana[i].second;
            if(x[c] < mx && y[c] < my) {
                ans = max(ans,mx+my+z[c]);
            }
        }
        for(int i = w; i <= r; i++) {
            int c = banana[i].second;
            yeah[pos[c]] = true;
            int l = n;
            if(calc1(0,n-1,1,y[c]) < pos[c]) {
                l = calc1(0,n-1,1,y[c]);
            }
            if(calc2(0,n-1,1,y[c]) > pos[c]) {
                l = min(l,pos[c]);
            }
            while(p > l) {
                p--;
                if(yeah[p]) {
                    mx = max(mx,x[p]);
                    my = max(my,y[p]);
                }
            }
            upd(0,n-1,1,pos[c],y[c]);
            if(c >= p) {
                mx = max(mx,x[c]);
                my = max(my,y[c]);
            }
        }
        w = r+1;
    }
    cout << ans;
    return 0;
}

• 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