Submission #561586

#	Time	Username	Problem	Language	Result	Execution time	Memory
561586		fatemetmhr	Team Contest (JOI22_team)	C++17	0 / 100	9 ms	19924 KiB

team

// Be name khoda //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define all(x) x.begin(), x.end()
#define fi     first
#define se     second

const int maxn5 = 2e5 + 10;
const int maxnt = 8e5 + 10;
const ll  inf   = 1e18;

int n;

struct segment_tree_bs{

    ll mx[maxnt];

    int get_first(int l, int r, int lq, int rq, ll val, int v){
        if(rq <= l || r <= lq || mx[v] <= val)
            return n;
        if(r - l == 1)
            return l;
        int mid = (l + r) >> 1;
        int ans = get_first(l, mid, lq, rq, val, v * 2);
        if(ans != n)
            return ans;
        return get_first(mid, r, lq, rq, val, v * 2 + 1);
    }

    ll get_max(int l, int r, int lq, int rq, int v){
        if(rq <= l || r <= lq)
            return -inf;
        if(lq <= l && r <= rq)
            return mx[v];
        int mid = (l + r) >> 1;
        return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1));
    }

    void update(int l, int r, int id, ll val, int v){
        if(r - l == 1){
            mx[v] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if(id < mid)
            update(l, mid, id, val, v * 2);
        else
            update(mid, r, id, val, v * 2 + 1);
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
        return;
    }

} val3_stored;

struct segment_tree_val2_plus_mx_val3{

    ll mxval2[maxnt], mxval3[maxnt], mx[maxnt];
    bool newval[maxnt];

    void build(){
        fill(mxval2, mxval2 + maxnt, -inf);
        fill(mxval3, mxval3 + maxnt, -inf);
        fill(mx, mx + maxnt, -inf);
        memset(newval, false, sizeof newval);
        return;
    }

    void shift(int v){
        if(!newval[v])
            return;
        newval[v] = false;
        mxval3[v * 2] = mxval3[v * 2 + 1] = mxval3[v];
        newval[v * 2] = newval[v * 2 + 1] = true;
        mx[v * 2] = mxval2[v * 2] + mxval3[v];
        mx[v * 2 + 1] = mxval2[v * 2 + 1] + mxval3[v];
        return;
    }

    void update_doone(int l, int r, int id, ll val, int v){
        if(r - l == 1){
            mxval2[v] = val;
            mx[v] = val + mxval3[v];
            return;
        }
        int mid = (l + r) >> 1; shift(v);
        if(id < mid)
            update_doone(l, mid, id, val, v * 2);
        else
            update_doone(mid, r, id, val, v * 2 + 1);
        mxval2[v] = max(mxval2[v * 2], mxval2[v * 2 + 1]);
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    }

    void sset(int l, int r, int lq, int rq, ll val, int v){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            newval[v] = true;
            mxval3[v] = val;
            mx[v] = val + mxval2[v];
            return;
        }
        int mid = (l + r) >> 1; shift(v);
        sset(l, mid, lq, rq, val, v * 2);
        sset(mid, r, lq, rq, val, v * 2 + 1);
        mx[v] = mx[v * 2] + mx[v * 2 + 1];
        return;
    }

    ll get_max(int l, int r, int lq, int rq, int v){
        if(rq <= l || r <= lq)
            return -inf;
        if(lq <= l && r <= rq)
            return mx[v];
        int mid = (l + r) >> 1; shift(v);
        return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1));
    }

} main_seg;

int pos2[maxn5], per1[maxn5], per2[maxn5];
ll bsval2[maxn5], val1[maxn5], val2[maxn5], val3[maxn5];
vector <int> toadd;

bool cmp1(int i, int j){return val1[i] < val1[j];}
bool cmp2(int i, int j){return val2[i] < val2[j];}

inline void add(int v){
    main_seg.update_doone(0, n, pos2[v], val2[v], 1);
    if(val3_stored.get_max(0, n, 0, pos2[v], 1) <= val3[v]){
        int last = val3_stored.get_first(0, n, pos2[v], n, val3[v] - 1, 1);
        main_seg.sset(0, n, pos2[v] + 1, last, val3[v], 1);
        main_seg.sset(0, n, pos2[v], pos2[v] + 1, -inf, 1);
    }
    val3_stored.update(0, n, pos2[v], val3[v], 1);
    return;
}

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

    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> val1[i] >> val2[i] >> val3[i];
        per1[i] = per2[i] = i;
    }

    sort(per1, per1 + n, cmp1); // bar hasbe val1
    sort(per2, per2 + n, cmp2); // bar hasbe val2

    for(int i = 0; i < n; i++){
        pos2[per2[i]] = i;
        bsval2[i] = val2[per2[i]];
    }

    main_seg.build(); // hame ro bezar -inf
    // val3_stored.build(0, n, 1); // hame ro bezar 0

    ll ans = -1;

    for(int i = 0; i < n; i++){
        int v = per1[i];
        while(toadd.size() && val1[toadd.back()] < val1[v]){
            add(toadd.back());
            toadd.pop_back();
        }
        int pt1 = upper_bound(bsval2, bsval2 + n, val2[v]) - bsval2;
        int pt2 = val3_stored.get_first(0, n, 0, n, val3[v], 1); // avalin kasi ke az akidan val3 bishtar darad, agar nabood n midahad

        int pt = max(pt1, pt2);

        ans = max(ans, main_seg.get_max(0, n, pt, n, 1) + val1[v]);

        toadd.pb(v);
    }

    cout << ans << endl;

}

• 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