Submission #1303072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303072		tonytung_123	Team Contest (JOI22_team)	C++20	0 / 100	49 ms	9168 KiB

team

#include <bits/stdc++.h>
#define task "Team Contest"
#define ll long long
#define fi first
#define se second
#define ld long double
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
using namespace std;

struct Node
{
    int x, y, z;
};

const int N = 15e4 + 5;
Node a[N];
pii mx1[N], mx2[N];
int n;
vector<int> node[N], bit[N];
vector<int> ys, zs;

void fakeUpd(int i, int j)
{
    for (int x = i; x > 0; x -= x&-x) node[x].push_back(j);
}

void fakeGet(int i, int j)
{
    for (int x = i; x <= ys.size(); x += x&-x) node[x].push_back(j);
}

void upd(int i, int j, int v)
{
    for (int x = i; x > 0; x -= x&-x)
        for (int y = lower_bound(all(node[x]), j)-node[x].begin()+1; y > 0; y -= y&-y) bit[x][y-1] = max(bit[x][y-1], v);
}

int get(int i, int j)
{
    int res = 0;
    for (int x = i; x <= ys.size(); x += x&-x)
        for (int y = lower_bound(all(node[x]), j)-node[x].begin()+1; y <= node[x].size(); y += y&-y) res = max(res, bit[x][y-1]);
    return res;
}

struct maxBIT
{
    vector<int> bit;
    int n;
    void init(int n_)
    {
        n = n_;
        bit.assign(n+1, 0);
    }
    void upd(int i, int v)
    {
        for (; i <= n; i += i&-i) bit[i] = max(bit[i], v);
    }
    int get(int i)
    {
        int res = 0;
        for (; i; i -= i&-i) res = max(res, bit[i]);
        return res;
    }
} mbit;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].x >> a[i].y >> a[i].z;
        ys.push_back(a[i].y);
        zs.push_back(a[i].z);
    }
    sort(all(ys));
    ys.erase(unique(all(ys)), ys.end());
    sort(all(zs));
    zs.erase(unique(all(zs)), zs.end());
    sort(a+1, a+n+1, [&](const Node &x, const Node &y){ return x.x < y.x; });
    for (int i = 1; i <= n; i++)
    {
        auto &[x, y, z] = a[i];
        y = lower_bound(all(ys), y) - ys.begin() + 1;
        z = lower_bound(all(zs), z) - zs.begin() + 1;
    }
    mbit.init(ys.size());
    for (int i = 1; i <= n; i++)
    {
        auto &[x, y, z] = a[i];
        mx1[i] = {y, mbit.get(y-1)};
        mbit.upd(y, z);
    }
    mbit.init(zs.size());
    for (int i = 1; i <= n; i++)
    {
        auto &[x, y, z] = a[i];
        mx2[i] = {mbit.get(z-1), z};
        mbit.upd(z, y);
    }
    for (int i = 1; i <= n; i++)
    {
        int y = mx1[i].fi, z = mx1[i].se;
        if (y && z) fakeUpd(y, z);
        y = mx2[i].fi, z = mx2[i].se;
        if (y && z) fakeUpd(y, z);
        fakeGet(y+1, z+1);
    }
    for (int i = 1; i <= ys.size(); i++)
    {
        sort(all(node[i]));
        node[i].erase(unique(all(node[i])), node[i].end());
        bit[i].resize(node[i].size());
    }
    int j = 1, res = 0;
    for (int i = 1; i <= n; i++)
    {
        auto &[x, y, z] = a[i];
        while (j <= n && a[j].x < x)
        {
            int y = mx1[j].fi, z = mx1[j].se;
            if (y && z) upd(y, z, ys[y-1]+zs[z-1]);
            y = mx2[j].fi, z = mx2[j].se;
            if (y && z) upd(y, z, ys[y-1]+zs[z-1]);
            j++;
        }
        int tmp = get(y+1, z+1);
        if (tmp) res = max(res, tmp+x);
    }
    cout << (res == 0 ? -1 : res);

    return 0;
}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
team.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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