Submission #1167669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167669		DangKhoizzzz	Team Contest (JOI22_team)	C++20	100 / 100	258 ms	21988 KiB

team

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

/*
+ array limit ???
+ special case ??? n = 1?
+ time limit ???
*/

using namespace std;

const int INF = 1e18 + 7;
const int maxn = 3e5;


struct Fenwick_Max
{
    int tree[maxn + 4];

    void update(int pos , int val)
    {
        while(pos <= maxn)
        {
            tree[pos] = max(tree[pos] , val);
            pos += (pos & (-pos));
        }
    }

    int get(int pos)
    {
        int res = 0;
        while(pos > 0)
        {
            res = max(res , tree[pos]);
            pos -= (pos & (-pos));
        }
        return res;
    }
};

Fenwick_Max bitx;
Fenwick_Max bity;

int n; arr3 a[maxn];
map <int , vector <pii>> mp;
vector <int> val;

void compress()
{
    for(int i = 1; i <= n; i++)
    {
        val.push_back(a[i][0]);
        val.push_back(a[i][1]);
    }
    sort(val.begin() , val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    for(int i = 1; i <= n; i++)
    {
        a[i][0] = upper_bound(val.begin() , val.end() , a[i][0]) - val.begin();
        a[i][1] = upper_bound(val.begin() , val.end() , a[i][1]) - val.begin();
        mp[a[i][2]].push_back({a[i][0] , a[i][1]});
    }
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    compress();

    int max_x = 0 , max_y = 0 , ans = -1;

    for(pair <int , vector <pii>> piv: mp)
    {
        int z = piv.fi;
        vector <pii> vp = piv.se;

        for(pii tmp: vp)
        {
            int x = tmp.fi;
            int y = tmp.se;
            if(x < max_x && y < max_y)
            {
                ans = max(ans , z + val[max_x - 1] + val[max_y - 1]);
            }
        }

        for(pii tmp: vp)
        {
            int x = tmp.fi;
            int y = tmp.se;

            if(bitx.get(x - 1) > y)
            {
                max_x = max(max_x , x);
                max_y = max(max_y , bitx.get(x - 1));
            }
            if(bity.get(y - 1) > x)
            {
                max_x = max(max_x , bity.get(y - 1));
                max_y = max(max_y , y);
            }
            bitx.update(x , y);
            bity.update(y , x);

        }
    }

    cout << ans << '\n';

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

team.cpp:15:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int INF = 1e18 + 7;
      |                 ~~~~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27