oj.uz

Submission #1026909

# Submission time Handle Problem Language Result Execution time Memory
1026909 2024-07-18T13:24:46 Z adaawf Team Contest (JOI22_team) C++17
0 / 100
 66 ms 23092 KB 
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
struct CONT {
    long long int a, b, c;
} a[150005], b[150005];
int za = 0, zb = 0, zc = 0, t[600005];
vector<int> va, vb, vc;
vector<CONT> g[150005];
long long int da[150005], db[150005], dc[150005];
map<int, int> ma, mb, mc;
bool cmp(CONT aa, CONT bb) {
    return aa.a < bb.a;
}
bool cmp2(CONT aa, CONT bb) {
    return aa.b < bb.b;
}
void Clear(int n) {
    for (int i = 1; i <= n * 4; i++) t[i] = 0;
}
void update(int v, int tl, int tr, int x, int y) {
    if (tl == tr) {
        t[v] = y;
        return;
    }
    int mid = (tl + tr) / 2;
    if (mid >= x) update(v * 2, tl, mid, x, y);
    else update(v * 2 + 1, mid + 1, tr, x, y);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return t[v];
    }
    int mid = (tl + tr) / 2;
    return max(sum(v * 2, tl, mid, l, min(r, mid)), sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r));
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a >> a[i].b >> a[i].c;
        va.push_back(a[i].a);
        vb.push_back(a[i].b);
        vc.push_back(a[i].c);
    }
    sort(va.begin(), va.end());
    sort(vb.begin(), vb.end());
    sort(vc.begin(), vc.end());
    for (int w : va) {
        if (!ma.count(w)) {
            ma[w] = ++za;
            da[za] = w;
        }
    }
    for (int w : vb) {
        if (!mb.count(w)) {
            mb[w] = ++zb;
            db[zb] = w;
        }
    }
    for (int w : vc) {
        if (!mc.count(w)) {
            mc[w] = ++zc;
            dc[zc] = w;
        }
    }
    for (int i = 1; i <= n; i++) {
        a[i].a = ma[a[i].a], a[i].b = mb[a[i].b], a[i].c = mc[a[i].c];
        b[i] = a[i];
    }
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + n + 1, cmp2);
    long long int res = -1;
    for (int i = 1; i <= n; i++) {
        long long int h = sum(1, 1, zb, 1, a[i].b - 1);
        if (h > a[i].c) g[a[i].b].push_back({a[i].a, a[i].b, h});
        update(1, 1, zb, a[i].b, a[i].c);
    }
    Clear(zb);
    for (int i = 1; i <= n; i++) {
        long long int h = sum(1, 1, zc, 1, a[i].c - 1);
        if (h > a[i].b) g[h].push_back({a[i].a, h, a[i].c});
        update(1, 1, zc, a[i].c, a[i].b);
    }
    Clear(zc);
    for (int i = 1; i <= n; i++) {
        if (b[i].b != b[i - 1].b) {
            for (auto w : g[b[i].b]) {
                //cout << i << " " << w.a << " " << w.b << " " << w.c << '\n';
                long long int h = sum(1, 1, zc, 1, w.c - 1);
                //cout << h << '\n';
                if (h > w.a) {
                    res = max(res, da[h] + db[w.b] + dc[w.c]);
                }
            }
        }
        update(1, 1, zc, b[i].c, b[i].a);
    }
    cout << res;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10716 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10720 KB Output is correct
11 Incorrect 66 ms 23092 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10716 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10720 KB Output is correct
11 Incorrect 66 ms 23092 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10716 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10720 KB Output is correct
11 Incorrect 66 ms 23092 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10716 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10720 KB Output is correct
11 Incorrect 66 ms 23092 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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