oj.uz

Submission #885687

# Submission time Handle Problem Language Result Execution time Memory
885687 2023-12-10T13:06:20 Z ByeWorld Team Contest (JOI22_team) C++14
0 / 100
 2 ms 14964 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 3e5+20;
const int LOG = 60;
const int MOD = 998244353;
const int SQRT = 520;
const int INF = 1e18;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
 
int n, N;
int a[MAXN], b[MAXN], c[MAXN];
vector <ipii> vec;
vector <int> x, y, z;

struct seg {
    int st[4*MAXN];
    seg()  { memset(st, -1, sizeof st); }
    int que(int id, int l, int r, int x, int y){
        if(x<=l && r<=y) return st[id];
        if(r<x || y<l) return -INF;
        return max(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
    }
    int upd(int id, int l, int r, int x, int y){
        if(l==r && l==x) return st[id] = max(st[id], y);
        if(r<x || x<l) return st[id];
        return st[id] = max(upd(lf, l, md, x, y), upd(rg, md+1, r, x, y));
    }
} A;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> N;
    for(int i=1; i<=N; i++){
        int x, y, z; cin >> x >> y >> z;
        vec.pb({{x, y}, z});
    }
    vec.pb({{-1, -1}, -1});
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    n = vec.size()-1;
    for(int i=1; i<=n; i++){
        a[i] = vec[i].fi.fi;
        b[i] = vec[i].fi.se;
        c[i] = vec[i].se;
    }
    vec.clear();
    // delete dobel

    x.pb(-1); y.pb(-1); z.pb(-1);
    for(int i=1; i<=n; i++){
        x.pb(a[i]); y.pb(b[i]); z.pb(c[i]);
    }
    sort(x.begin(), x.end()); x.resize(unique(x.begin(), x.end()) - x.begin());
    sort(y.begin(), y.end()); y.resize(unique(y.begin(), y.end()) - y.begin());
    sort(z.begin(), z.end()); z.resize(unique(z.begin(), z.end()) - z.begin());
    for(int i=1; i<=n; i++){
        a[i] = lower_bound(x.begin(), x.end(), a[i]) - x.begin();
        b[i] = lower_bound(y.begin(), y.end(), b[i]) - y.begin();
        c[i] = lower_bound(z.begin(), z.end(), c[i]) - z.begin();
        vec.pb({{a[i], b[i]}, c[i]});
    }
    vec.pb({{-1, -1}, -1});
    sort(vec.begin(), vec.end());
    //for(auto in : vec) cout << in.fi.fi << ' '<<in.fi.se << ' ' <<in.se << " in\n";

    int ans = -1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i-1; j++){
            if(vec[i].fi.fi <= vec[j].fi.fi && vec[j].fi.se <= vec[i].fi.se) continue; // bj <= bi
            int idx = A.que(1, 1, n, 1, vec[j].fi.se-1);
            //cout << i << ' '<< j << ' ' << idx << " idx\n";
            if(idx < 0 || idx < vec[i].se || idx < vec[j].se) continue;
            int te = x[vec[i].fi.fi] + y[vec[j].fi.se] + z[idx];
            ans = max(ans, te);
        }
        A.upd(1, 1, n, vec[i].fi.se, vec[i].se);
    }
    cout << ans << '\n';
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14964 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Incorrect 2 ms 14940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14964 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Incorrect 2 ms 14940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14936 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Incorrect 2 ms 14940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14936 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Incorrect 2 ms 14940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14936 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Incorrect 2 ms 14940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14936 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Incorrect 2 ms 14940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14964 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Incorrect 2 ms 14940 KB Output isn't correct
6 Halted 0 ms 0 KB -