제출 #637379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637379		tht2005	Team Contest (JOI22_team)	C++17	0 / 100	2126 ms	519632 KiB

team

#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
• Subtask 2: 0 / 29
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27