Submission #915613

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915613	2024-01-24T10:39:57 Z	LOLOLO	Team Contest (JOI22_team)	C++17	9 / 100	100 ms	14496 KB

team

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #915613

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 29.0

Subtask #3 9.0 / 9.0

Subtask #4 0 / 9.0

Subtask #5 0 / 9.0

Subtask #6 0 / 9.0

Subtask #7 0 / 27.0

Subtask #1
0 / 8.0

Subtask #2
0 / 29.0

Subtask #3
9.0 / 9.0

Subtask #4
0 / 9.0

Subtask #5
0 / 9.0

Subtask #6
0 / 9.0

Subtask #7
0 / 27.0