oj.uz

Submission #637379

# Submission time Handle Problem Language Result Execution time Memory
637379 2022-09-01T14:49:01 Z tht2005 Team Contest (JOI22_team) C++17
0 / 100
 2000 ms 519632 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(XX[i].a[2], y);
                }
                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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8532 KB Output is correct
2 Correct 7 ms 8532 KB Output is correct
3 Correct 7 ms 8564 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 7 ms 8532 KB Output is correct
6 Correct 9 ms 8516 KB Output is correct
7 Correct 9 ms 8612 KB Output is correct
8 Correct 8 ms 8532 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 7 ms 8560 KB Output is correct
11 Correct 6 ms 8568 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 9656 KB Output is correct
15 Incorrect 13 ms 9432 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8532 KB Output is correct
2 Correct 7 ms 8532 KB Output is correct
3 Correct 7 ms 8564 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 7 ms 8532 KB Output is correct
6 Correct 9 ms 8516 KB Output is correct
7 Correct 9 ms 8612 KB Output is correct
8 Correct 8 ms 8532 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 7 ms 8560 KB Output is correct
11 Correct 6 ms 8568 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 9656 KB Output is correct
15 Incorrect 13 ms 9432 KB Output isn't correct
16 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 8 ms 8516 KB Output is correct
3 Correct 7 ms 8516 KB Output is correct
4 Correct 7 ms 8564 KB Output is correct
5 Correct 7 ms 8524 KB Output is correct
6 Correct 9 ms 8440 KB Output is correct
7 Correct 10 ms 8532 KB Output is correct
8 Correct 7 ms 8520 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 7 ms 8532 KB Output is correct
11 Execution timed out 2126 ms 519632 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 8 ms 8516 KB Output is correct
3 Correct 7 ms 8516 KB Output is correct
4 Correct 7 ms 8564 KB Output is correct
5 Correct 7 ms 8524 KB Output is correct
6 Correct 9 ms 8440 KB Output is correct
7 Correct 10 ms 8532 KB Output is correct
8 Correct 7 ms 8520 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 7 ms 8532 KB Output is correct
11 Execution timed out 2126 ms 519632 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 8 ms 8516 KB Output is correct
3 Correct 7 ms 8516 KB Output is correct
4 Correct 7 ms 8564 KB Output is correct
5 Correct 7 ms 8524 KB Output is correct
6 Correct 9 ms 8440 KB Output is correct
7 Correct 10 ms 8532 KB Output is correct
8 Correct 7 ms 8520 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 7 ms 8532 KB Output is correct
11 Execution timed out 2126 ms 519632 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 8 ms 8516 KB Output is correct
3 Correct 7 ms 8516 KB Output is correct
4 Correct 7 ms 8564 KB Output is correct
5 Correct 7 ms 8524 KB Output is correct
6 Correct 9 ms 8440 KB Output is correct
7 Correct 10 ms 8532 KB Output is correct
8 Correct 7 ms 8520 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 7 ms 8532 KB Output is correct
11 Execution timed out 2126 ms 519632 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8532 KB Output is correct
2 Correct 7 ms 8532 KB Output is correct
3 Correct 7 ms 8564 KB Output is correct
4 Correct 7 ms 8532 KB Output is correct
5 Correct 7 ms 8532 KB Output is correct
6 Correct 9 ms 8516 KB Output is correct
7 Correct 9 ms 8612 KB Output is correct
8 Correct 8 ms 8532 KB Output is correct
9 Correct 7 ms 8532 KB Output is correct
10 Correct 7 ms 8560 KB Output is correct
11 Correct 6 ms 8568 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 9656 KB Output is correct
15 Incorrect 13 ms 9432 KB Output isn't correct
16 Halted 0 ms 0 KB -