Submission #915614

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915614	2024-01-24T10:41:04 Z	LOLOLO	Team Contest (JOI22_team)	C++17	9 / 100	96 ms	13368 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 || u > 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 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	0 ms	348 KB	Output is correct
13	Correct	0 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 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	0 ms	348 KB	Output is correct
13	Correct	0 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	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 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	1 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	1 ms	348 KB	Output is correct
11	Correct	75 ms	13192 KB	Output is correct
12	Correct	49 ms	9048 KB	Output is correct
13	Correct	60 ms	10836 KB	Output is correct
14	Correct	76 ms	13368 KB	Output is correct
15	Correct	51 ms	13136 KB	Output is correct
16	Correct	36 ms	13148 KB	Output is correct

Subtask #4
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 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	1 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	1 ms	348 KB	Output is correct
11	Correct	75 ms	13192 KB	Output is correct
12	Correct	49 ms	9048 KB	Output is correct
13	Correct	60 ms	10836 KB	Output is correct
14	Correct	76 ms	13368 KB	Output is correct
15	Correct	51 ms	13136 KB	Output is correct
16	Correct	36 ms	13148 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	500 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	2 ms	604 KB	Output is correct
22	Correct	96 ms	13288 KB	Output is correct
23	Correct	86 ms	12856 KB	Output is correct
24	Correct	63 ms	9648 KB	Output is correct
25	Incorrect	87 ms	13136 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	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 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	1 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	1 ms	348 KB	Output is correct
11	Correct	75 ms	13192 KB	Output is correct
12	Correct	49 ms	9048 KB	Output is correct
13	Correct	60 ms	10836 KB	Output is correct
14	Correct	76 ms	13368 KB	Output is correct
15	Correct	51 ms	13136 KB	Output is correct
16	Correct	36 ms	13148 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	500 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	2 ms	604 KB	Output is correct
22	Correct	96 ms	13288 KB	Output is correct
23	Correct	86 ms	12856 KB	Output is correct
24	Correct	63 ms	9648 KB	Output is correct
25	Incorrect	87 ms	13136 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	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 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	1 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	1 ms	348 KB	Output is correct
11	Correct	75 ms	13192 KB	Output is correct
12	Correct	49 ms	9048 KB	Output is correct
13	Correct	60 ms	10836 KB	Output is correct
14	Correct	76 ms	13368 KB	Output is correct
15	Correct	51 ms	13136 KB	Output is correct
16	Correct	36 ms	13148 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	500 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	2 ms	604 KB	Output is correct
22	Correct	96 ms	13288 KB	Output is correct
23	Correct	86 ms	12856 KB	Output is correct
24	Correct	63 ms	9648 KB	Output is correct
25	Incorrect	87 ms	13136 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 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	0 ms	348 KB	Output is correct
13	Correct	0 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 #915614

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