Submission #1187290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187290		quannnguyen2009	Team Contest (JOI22_team)	C++20	0 / 100	0 ms	328 KiB

team

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N=1.5e5+5, mod = 1e9+7, inf = 1e18;

struct SegTreeMin {
    int sz;
    vector<int> seg;
    SegTreeMin(int n) {
        sz = n;
        seg.resize(4*n+5, inf);
    }
    void upd(int node, int l, int r, int idx, int val) {
        if(l>idx || r<idx) return;
        if(l==r) {
            seg[node] = val;
            return;
        }
        int mid = (l+r)>>1;
        upd(node<<1, l, mid, idx, val); upd(node<<1|1, mid+1, r, idx, val);
        seg[node] = min(seg[node<<1], seg[node<<1|1]);
    }
    int get(int node, int l, int r, int ql, int qr) {
        if(l>qr || r<ql) return inf;
        if(ql<=l && r<=qr) return seg[node];
        int mid = (l+r)>>1;
        return min(get(node<<1, l, mid, ql, qr), get(node<<1|1, mid+1, r, ql, qr));
    }

    int walk(int node, int l, int r, int val) {
        if(l==r) {
            if(seg[node]<val) return l;
            return -1;
        }
        int mid = (l+r)>>1;
        if(seg[node<<1|1]<val) {
            return walk(node<<1|1, mid+1, r, val);
        } else if(seg[node<<1]<val) {
            return walk(node<<1, l, mid, val);
        } else {
            return -1;
        }
    }
};

struct SegTreeMax {
    int sz;
    vector<int> seg;
    SegTreeMax(int n) {
        sz = n;
        seg.resize(4*n+5, -inf);
    }
    void upd(int node, int l, int r, int idx, int val) {
        if(l>idx || r<idx) return;
        if(l==r) {
            seg[node] = val;
            return;
        }
        int mid = (l+r)>>1;
        upd(node<<1, l, mid, idx, val); upd(node<<1|1, mid+1, r, idx, val);
        seg[node] = max(seg[node<<1], seg[node<<1|1]);
    }
    int get(int node, int l, int r, int ql, int qr) {
        if(l>qr || r<ql) return -inf;
        if(ql<=l && r<=qr) return seg[node];
        int mid = (l+r)>>1;
        return max(get(node<<1, l, mid, ql, qr), get(node<<1|1, mid+1, r, ql, qr));
    }
    int walk(int node, int l, int r, int val) {
        if(l==r) {
            if(seg[node]>val) return l;
            return -1;
        }
        int mid = (l+r)>>1;
        if(seg[node<<1|1]>val) {
            return walk(node<<1|1, mid+1, r, val);
        } else if(seg[node<<1]>val) {
            return walk(node<<1, l, mid, val);
        } else {
            return -1;
        }
    }
};

struct Item {
    int x, y, z;
    bool operator<(Item o) const {
        return x<o.z;        
    }
} a[N];

int n, m, ans;
vector<int> v;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    v.pb(0);
    for (int i=1; i<=n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].z;
        v.pb(a[i].x); v.pb(a[i].y); v.pb(a[i].z);
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    for (int i=1; i<=n; i++) {
        a[i].x = lower_bound(all(v), a[i].x)-v.begin();
        a[i].y = lower_bound(all(v), a[i].y)-v.begin();
        a[i].z = lower_bound(all(v), a[i].z)-v.begin();
    }
    sort(a+1, a+n+1);
    m = sz(v)-1;
    SegTreeMax s1(m), s2(m);
    SegTreeMin s3(m);
    int idx = 1;
    for (int i=1; i<=n; i++) {
        while (a[idx].x<a[i].x) {
            s1.upd(1, 1, m, a[idx].y, a[idx].z);
            s3.upd(1, 1, m, a[idx].y, a[idx].z);
            int tmp = s1.get(1, 1, m, 1, a[idx].y-1);
            if(tmp>a[idx].z) s2.upd(1, 1, m, a[idx].y, tmp);
            tmp = s3.walk(1, 1, m, a[idx].z);
            if(tmp!=-1) s2.upd(1, 1, m, tmp, a[idx].z);
            idx++;
        }
        int tmp = s2.walk(1, 1, m, a[i].z);
        if(tmp!=-1) ans = max(ans, v[a[i].x]+v[tmp]+v[s2.get(1, 1, m, tmp, m)]);
    }
    if(ans) cout << ans;
    else cout << -1;
}

• 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