oj.uz

Submission #637382

# Submission time Handle Problem Language Result Execution time Memory
637382 2022-09-01T14:56:29 Z tht2005 Team Contest (JOI22_team) C++17
8 / 100
 2000 ms 521348 KB 
#include <bits/stdc++.h>

using namespace std;

int rd() {
    bool neg = 0; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if(c == '-') neg = !neg;
    int n = 0; while('0' <= c && c <= '9') n = (n << 3) + (n << 1) + c - '0', c = getchar();
    return neg ? -n : n;
}
void wr(int n) {
    static char o[11];
    if(n < 0) putchar('-'), n = -n;
    int i = 0; do o[i++] = n % 10 + '0'; while(n /= 10);
    while(i--) putchar(o[i]);
}

#define N 150005

struct dt {
    int a[3];
    bool operator< (const dt& b) const {
        return a[0] < b.a[0];
    }
} XX[N];

struct bit2d {
    vector<int> node[N], f[N];
    void fake_update(int x, int yy) {
        for(; x >= 0; x = (x & (x + 1)) - 1) {
            for(int y = yy; y >= 0; y = (y & (y + 1)) - 1) {
                node[x].push_back(y);
            }
        }
    }
    void fake_query(int x, int yy) {
        for(; x < N; x |= x + 1) {
            for(int y = yy; y < N; y |= y + 1) {
                node[x].push_back(y);
            }
        }
    }
    void init(bool t) {
        for(int i = 0; i < N; ++i) {
            vector<int>& v = node[i];
            if(t) {
                sort(v.begin(), v.end());
                v.erase(unique(v.begin(), v.end()), v.end());
            }
            f[i].assign(v.size(), -1);
        }
    }
    void update(int x, int yy, int d) {
        for(; x >= 0; x = (x & (x + 1)) - 1) {
            for(int y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin(); y >= 0; y = (y & (y + 1)) - 1) {
                f[x][y] = max(f[x][y], d);
            }
        }
    }
    int query(int x, int yy) {
        int res = -1;
        for(; x < N; x |= x + 1) {
            for(int y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin(); y < (int)node[x].size(); y |= y + 1) {
                res = max(res, f[x][y]);
            }
        }
        return res;
    }
} f;

struct bit {
    int f[N];
    void init() {
        memset(f, 0xff, sizeof(f));
    }
    void update(int x, int d) {
        for(; x < N; x |= x + 1) {
            f[x] = max(f[x], d);
        }
    }
    int query(int x) {
        int res = -1;
        for(; x >= 0; x = (x & (x + 1)) - 1) {
            res = max(res, f[x]);
        }
        return res;
    }
} g, h;

int main() {
    int n = rd();
    vector<int> vect[3];
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < 3; ++j) {
            XX[i].a[j] = rd();
            vect[j].push_back(XX[i].a[j]);
        }
    }
    for(int i = 0; i < 3; ++i) {
        vector<int>& v = vect[i];
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < 3; ++j) {
            XX[i].a[j] = lower_bound(vect[j].begin(), vect[j].end(), XX[i].a[j]) - vect[j].begin();
        }
    }
    for(int t = 0; t < 3; ++t) {
        if(t) {
            for(int i = 0; i < n; ++i) {
                swap(XX[i].a[0], XX[i].a[t]);
            }
        }
        sort(XX, XX + n);
        g.init();
        h.init();
        for(int i = 0, j = 0; i < n;) {
            while(j < n && XX[i].a[0] == XX[j].a[0]) {
                f.fake_query(XX[j].a[1] + 1, XX[j].a[2] + 1);
                ++j;
            }
            for(; i < j; ++i) {
                int z = g.query(XX[i].a[1] - 1);
                if(XX[i].a[2] < z) {
                    f.fake_update(XX[i].a[1], z);
                }
                int y = h.query(XX[i].a[2] - 1);
                if(XX[i].a[1] < y) {
                    f.fake_update(y, XX[i].a[2]);
                }
                g.update(XX[i].a[1], XX[i].a[2]);
                h.update(XX[i].a[2], XX[i].a[1]);
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        swap(XX[i].a[0], XX[i].a[1]);
        swap(XX[i].a[1], XX[i].a[2]);
    }
    int res = -1;
    for(int t = 0; t < 3; ++t) {
        if(t) {
            vect[0].swap(vect[t]);
            for(int i = 0; i < n; ++i) {
                swap(XX[i].a[0], XX[i].a[t]);
            }
        }
        sort(XX, XX + n);
        f.init(t == 0);
        g.init();
        h.init();
        for(int i = 0, j = 0; i < n;) {
            while(j < n && XX[i].a[0] == XX[j].a[0]) {
                int tmp = f.query(XX[j].a[1] + 1, XX[j].a[2] + 1);
                if(tmp != -1) {
                    res = max(res, vect[0][XX[j].a[0]] + tmp);
                }
                ++j;
            }
            for(; i < j; ++i) {
                int z = g.query(XX[i].a[1] - 1);
                if(XX[i].a[2] < z) {
                    f.update(XX[i].a[1], z, vect[1][XX[i].a[1]] + vect[2][z]);
                }
                int y = h.query(XX[i].a[2] - 1);
                if(XX[i].a[1] < y) {
                    f.update(y, XX[i].a[2], vect[1][y] + vect[2][XX[i].a[2]]);
                }
                g.update(XX[i].a[1], XX[i].a[2]);
                h.update(XX[i].a[2], XX[i].a[1]);
            }
        }
    }
    printf("%d", res);
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 6 ms 8532 KB Output is correct
3 Correct 6 ms 8532 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 6 ms 8532 KB Output is correct
6 Correct 6 ms 8532 KB Output is correct
7 Correct 7 ms 8532 KB Output is correct
8 Correct 6 ms 8532 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 6 ms 8532 KB Output is correct
11 Correct 6 ms 8532 KB Output is correct
12 Correct 7 ms 8532 KB Output is correct
13 Correct 6 ms 8532 KB Output is correct
14 Correct 15 ms 9568 KB Output is correct
15 Correct 12 ms 9428 KB Output is correct
16 Correct 16 ms 9504 KB Output is correct
17 Correct 13 ms 9428 KB Output is correct
18 Correct 14 ms 9556 KB Output is correct
19 Correct 15 ms 9652 KB Output is correct
20 Correct 14 ms 9540 KB Output is correct
21 Correct 13 ms 9488 KB Output is correct
22 Correct 13 ms 9448 KB Output is correct
23 Correct 14 ms 9812 KB Output is correct
24 Correct 12 ms 9416 KB Output is correct
25 Correct 13 ms 9408 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 6 ms 8532 KB Output is correct
3 Correct 6 ms 8532 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 6 ms 8532 KB Output is correct
6 Correct 6 ms 8532 KB Output is correct
7 Correct 7 ms 8532 KB Output is correct
8 Correct 6 ms 8532 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 6 ms 8532 KB Output is correct
11 Correct 6 ms 8532 KB Output is correct
12 Correct 7 ms 8532 KB Output is correct
13 Correct 6 ms 8532 KB Output is correct
14 Correct 15 ms 9568 KB Output is correct
15 Correct 12 ms 9428 KB Output is correct
16 Correct 16 ms 9504 KB Output is correct
17 Correct 13 ms 9428 KB Output is correct
18 Correct 14 ms 9556 KB Output is correct
19 Correct 15 ms 9652 KB Output is correct
20 Correct 14 ms 9540 KB Output is correct
21 Correct 13 ms 9488 KB Output is correct
22 Correct 13 ms 9448 KB Output is correct
23 Correct 14 ms 9812 KB Output is correct
24 Correct 12 ms 9416 KB Output is correct
25 Correct 13 ms 9408 KB Output is correct
26 Correct 152 ms 21984 KB Output is correct
27 Incorrect 146 ms 22012 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 6 ms 8532 KB Output is correct
3 Correct 7 ms 8532 KB Output is correct
4 Correct 8 ms 8556 KB Output is correct
5 Correct 7 ms 8560 KB Output is correct
6 Correct 8 ms 8552 KB Output is correct
7 Correct 7 ms 8532 KB Output is correct
8 Correct 6 ms 8532 KB Output is correct
9 Correct 6 ms 8532 KB Output is correct
10 Correct 7 ms 8532 KB Output is correct
11 Execution timed out 2111 ms 521348 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 6 ms 8532 KB Output is correct
3 Correct 7 ms 8532 KB Output is correct
4 Correct 8 ms 8556 KB Output is correct
5 Correct 7 ms 8560 KB Output is correct
6 Correct 8 ms 8552 KB Output is correct
7 Correct 7 ms 8532 KB Output is correct
8 Correct 6 ms 8532 KB Output is correct
9 Correct 6 ms 8532 KB Output is correct
10 Correct 7 ms 8532 KB Output is correct
11 Execution timed out 2111 ms 521348 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 6 ms 8532 KB Output is correct
3 Correct 7 ms 8532 KB Output is correct
4 Correct 8 ms 8556 KB Output is correct
5 Correct 7 ms 8560 KB Output is correct
6 Correct 8 ms 8552 KB Output is correct
7 Correct 7 ms 8532 KB Output is correct
8 Correct 6 ms 8532 KB Output is correct
9 Correct 6 ms 8532 KB Output is correct
10 Correct 7 ms 8532 KB Output is correct
11 Execution timed out 2111 ms 521348 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 6 ms 8532 KB Output is correct
3 Correct 7 ms 8532 KB Output is correct
4 Correct 8 ms 8556 KB Output is correct
5 Correct 7 ms 8560 KB Output is correct
6 Correct 8 ms 8552 KB Output is correct
7 Correct 7 ms 8532 KB Output is correct
8 Correct 6 ms 8532 KB Output is correct
9 Correct 6 ms 8532 KB Output is correct
10 Correct 7 ms 8532 KB Output is correct
11 Execution timed out 2111 ms 521348 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 6 ms 8532 KB Output is correct
3 Correct 6 ms 8532 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 6 ms 8532 KB Output is correct
6 Correct 6 ms 8532 KB Output is correct
7 Correct 7 ms 8532 KB Output is correct
8 Correct 6 ms 8532 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 6 ms 8532 KB Output is correct
11 Correct 6 ms 8532 KB Output is correct
12 Correct 7 ms 8532 KB Output is correct
13 Correct 6 ms 8532 KB Output is correct
14 Correct 15 ms 9568 KB Output is correct
15 Correct 12 ms 9428 KB Output is correct
16 Correct 16 ms 9504 KB Output is correct
17 Correct 13 ms 9428 KB Output is correct
18 Correct 14 ms 9556 KB Output is correct
19 Correct 15 ms 9652 KB Output is correct
20 Correct 14 ms 9540 KB Output is correct
21 Correct 13 ms 9488 KB Output is correct
22 Correct 13 ms 9448 KB Output is correct
23 Correct 14 ms 9812 KB Output is correct
24 Correct 12 ms 9416 KB Output is correct
25 Correct 13 ms 9408 KB Output is correct
26 Correct 152 ms 21984 KB Output is correct
27 Incorrect 146 ms 22012 KB Output isn't correct
28 Halted 0 ms 0 KB -