oj.uz

답안 #915613

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915613 2024-01-24T10:39:57 Z LOLOLO Team Contest (JOI22_team) C++17
9 / 100
 100 ms 14496 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 3e5 + 10;
struct segtree{
    vector <int> seg;
    void ass(int n) {
        seg.assign(n * 4 + 100, 0);
    }

    void upd(int id, int l, int r, int p, int v) {
        if (l > p || r < p)
            return;

        seg[id] = max(seg[id], v);
        if (l == r)
            return;

        int m = (l + r) / 2;
        upd(id * 2, l, m, p, v);
        upd(id * 2 + 1, m + 1, r, p, v);
    }

    int get(int id, int l, int r, int u, int v) {
        if (r < u || l > v)
            return 0;

        if (l >= u && r <= v)
            return seg[id];

        int m = (l + r) / 2;
        return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
    }
};

segtree s1, s2;
map <int, int> mp1, mp2;
pair <int, int> best;
int n, sz;

void add(int u, int v) {
    int se = s1.get(1, 1, sz, 1, mp1[u] - 1);
    if (se > v) {
        best = max(best, {u, se});
    }

    int fi = s2.get(1, 1, sz, 1, mp2[v] - 1);
    if (fi > u) {
        best = max(best, {fi, u});
    }

    s1.upd(1, 1, sz, mp1[u], v);
    s2.upd(1, 1, sz, mp2[v], u);
}

ll solve() {
    cin >> n;
    sz = n + 10;
    s1.ass(n + 10);
    s2.ass(n + 10);

    vector < vector <int>> v(n);
    for (auto &x : v) {
        x.resize(3);
        cin >> x[0] >> x[1] >> x[2];
        mp1[x[1]];
        mp2[x[2]];
    }

    int t1 = 1, t2 = 1;
    for (auto &x : mp1) {
        x.s = t1++;
    }

    for (auto &x : mp2) {
        x.s = t2++;
    }

    sort(all(v));
    int j = 0, ans = -1;

    for (int i = 0; i < n; i++) {
        while (v[j][0] < v[i][0]) {
            add(v[j][1], v[j][2]);
            j++;
        }

        if (best.f > v[i][1] && best.s > v[i][2]) {
            ans = max(ans, best.f + best.s + v[i][0]);
        }
    }

    return ans;
}

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

    int t = 1;
    //cin >> t;
    while (t--) {
        cout << solve() << '\n';
    }

    return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 1 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 1 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 80 ms 13596 KB Output is correct
12 Correct 52 ms 9052 KB Output is correct
13 Correct 52 ms 11788 KB Output is correct
14 Correct 72 ms 14160 KB Output is correct
15 Correct 61 ms 14252 KB Output is correct
16 Correct 37 ms 14164 KB Output is correct

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 80 ms 13596 KB Output is correct
12 Correct 52 ms 9052 KB Output is correct
13 Correct 52 ms 11788 KB Output is correct
14 Correct 72 ms 14160 KB Output is correct
15 Correct 61 ms 14252 KB Output is correct
16 Correct 37 ms 14164 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 97 ms 14496 KB Output is correct
23 Correct 100 ms 14168 KB Output is correct
24 Correct 65 ms 10592 KB Output is correct
25 Incorrect 94 ms 14420 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 80 ms 13596 KB Output is correct
12 Correct 52 ms 9052 KB Output is correct
13 Correct 52 ms 11788 KB Output is correct
14 Correct 72 ms 14160 KB Output is correct
15 Correct 61 ms 14252 KB Output is correct
16 Correct 37 ms 14164 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 97 ms 14496 KB Output is correct
23 Correct 100 ms 14168 KB Output is correct
24 Correct 65 ms 10592 KB Output is correct
25 Incorrect 94 ms 14420 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 80 ms 13596 KB Output is correct
12 Correct 52 ms 9052 KB Output is correct
13 Correct 52 ms 11788 KB Output is correct
14 Correct 72 ms 14160 KB Output is correct
15 Correct 61 ms 14252 KB Output is correct
16 Correct 37 ms 14164 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 97 ms 14496 KB Output is correct
23 Correct 100 ms 14168 KB Output is correct
24 Correct 65 ms 10592 KB Output is correct
25 Incorrect 94 ms 14420 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 1 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -