oj.uz

Submission #885696

# Submission time Handle Problem Language Result Execution time Memory
885696 2023-12-10T13:39:55 Z ByeWorld Team Contest (JOI22_team) C++14
0 / 100
 31 ms 19644 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

    //coor compress
    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, las = 0;
    for(int i=1; i<=n; i++){
        if(vec[i].fi.fi != vec[i-1].fi.fi){
            for(int j=las+1; j<=i-1; j++){
                A.upd(1, 1, n, vec[j].fi.se, vec[j].se);
            }
            las = i-1;
        }

        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);
            if(idx < 0 || idx <= max(vec[i].se, vec[j].se)) continue;
            //cout << i << ' '<< j << ' ' << idx << " idx\n";
            int te = x[vec[i].fi.fi] + y[vec[j].fi.se] + z[idx];
            //int te = vec[i].fi.fi + vec[j].fi.se + idx;
            ans = max(ans, te);
        }
    }
    cout << ans << '\n';
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 2 ms 14936 KB Output is correct
10 Correct 2 ms 14940 KB Output is correct
11 Correct 2 ms 14940 KB Output is correct
12 Correct 2 ms 14940 KB Output is correct
13 Correct 2 ms 14980 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Incorrect 2 ms 14940 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 2 ms 14936 KB Output is correct
10 Correct 2 ms 14940 KB Output is correct
11 Correct 2 ms 14940 KB Output is correct
12 Correct 2 ms 14940 KB Output is correct
13 Correct 2 ms 14980 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Incorrect 2 ms 14940 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14972 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14936 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 2 ms 14936 KB Output is correct
11 Correct 31 ms 19644 KB Output is correct
12 Incorrect 21 ms 17352 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14972 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14936 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 2 ms 14936 KB Output is correct
11 Correct 31 ms 19644 KB Output is correct
12 Incorrect 21 ms 17352 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14972 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14936 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 2 ms 14936 KB Output is correct
11 Correct 31 ms 19644 KB Output is correct
12 Incorrect 21 ms 17352 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14972 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14936 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 2 ms 14936 KB Output is correct
11 Correct 31 ms 19644 KB Output is correct
12 Incorrect 21 ms 17352 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 2 ms 14936 KB Output is correct
10 Correct 2 ms 14940 KB Output is correct
11 Correct 2 ms 14940 KB Output is correct
12 Correct 2 ms 14940 KB Output is correct
13 Correct 2 ms 14980 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Incorrect 2 ms 14940 KB Output isn't correct
16 Halted 0 ms 0 KB -