제출 #1217423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217423		jerzyk	Team Contest (JOI22_team)	C++20	100 / 100	93 ms	5660 KiB

team

#include<bits/stdc++.h>

using namespace std;
#define nd second
#define st first
#define pb push_back
typedef long long ll;
typedef long double ld;
const int N = 1<<18;
pair<int, pair<int, int>> tab[N];
pair<int, int> sk[N];
int drzy[2 * N], drzz[2 * N];

void AddY(int v, int il)
{
    v += N;
    while(v > 0)
    {drzy[v] = max(drzy[v], il); v /= 2;}
}

void AddZ(int v, int il)
{
    v += N;
    while(v > 0)
    {drzz[v] = max(drzz[v], il); v /= 2;}
}

int MaxY(int a, int b)
{
    a += N; b += N;
    int w = max(drzy[a], drzy[b]);
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0) w = max(w, drzy[a + 1]);
        if(b % 2 == 1) w = max(w, drzy[b - 1]);
        a /= 2; b /= 2;
    }
    return w;
}

int MaxZ(int a, int b)
{
    a += N; b += N;
    int w = max(drzy[a], drzz[b]);
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0) w = max(w, drzz[a + 1]);
        if(b % 2 == 1) w = max(w, drzz[b - 1]);
        a /= 2; b /= 2;
    }
    return w;
}

void Skaluj(int n)
{
    int l = 0;
    vector<pair<int, int>> v;
    for(int i = 1; i <= n; ++i)
        v.pb(make_pair(tab[i].nd.st, i));
    sort(v.begin(), v.end());
    for(int i = 0; i < n; ++i)
    {
        if(i == 0 || v[i].st != v[i - 1].st) ++l;
        sk[v[i].nd].st = l;
    }
    v.clear(); l = 0;
    for(int i = 1; i <= n; ++i)
        v.pb(make_pair(tab[i].nd.nd, i));
    sort(v.begin(), v.end());
    for(int i = 0; i < n; ++i)
    {
        if(i == 0 || v[i].st != v[i - 1].st) ++l;
        sk[v[i].nd].nd = l;
    }
}

void Solve()
{
    int n, p = 1;
    pair<int, int> am = make_pair(0, 0), ca;
    pair<int, pair<int, pair<int, int>>> ans = make_pair(-1, make_pair(0, make_pair(0, 0)));
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> tab[i].st >> tab[i].nd.st >> tab[i].nd.nd;
    sort(tab + 1, tab + 1 + n);
    Skaluj(n);
    for(int i = 1; i <= n; ++i)
    {
        //cout << "d: " << tab[i].st << " " << tab[i].nd.st << " " << tab[i].nd.nd << "\n";
        //cout << sk[i].st << " " << sk[i].nd << " : " << am.st << " " << am.nd << "\n";
        if(am.st != 0)
            if(am.st > tab[i].nd.st  && am.nd > tab[i].nd.nd)
                ans = max(ans, make_pair(tab[i].st + am.st + am.nd, make_pair(tab[i].st, am)));
        if(tab[i].st != tab[i + 1].st)
        {
            for(int j = p; j <= i; ++j)
            {
                ca = make_pair(tab[j].nd.st, MaxZ(0, sk[j].st - 1));
                if(ca.nd > tab[j].nd.nd && ca.st != 0 && ca.st >= am.st) am = max(am, ca);
                ca = make_pair(MaxY(0, sk[j].nd - 1), tab[j].nd.nd);
                if(ca.st > tab[j].nd.st && ca.nd != 0 && ca.st >= am.st) am = max(am, ca);
                AddY(sk[j].nd, tab[j].nd.st);
                AddZ(sk[j].st, tab[j].nd.nd);
            }
            p = i + 1;
        }
    }
    cout << ans.st << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();

    return 0;
}

• 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