Submission #925789

#	Time	Username	Problem	Language	Result	Execution time	Memory
925789		andrei_boaca	Team Contest (JOI22_team)	C++17	100 / 100	643 ms	35012 KiB

team

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
const int INF=1e9;
int lim=500;
int n;
struct point
{
    int x,y,z;
} v[150005];
bool byx(point a,point b)
{
    return a.x<b.x;
}
bool byy(pii a,pii b)
{
    if(a.first!=b.first)
        return a.first>b.first;
    return a.second<b.second;
}
bool byz(pii a,pii b)
{
    if(a.second!=b.second)
        return a.second>b.second;
    return a.first<b.first;
}
vector<pii> enable[150005];
map<pii,int> pozmin;
map<int,int> nrm;
int nrz;
int arb[4*150005];
void build(int nod,int st,int dr)
{
    arb[nod]=INF;
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void update(int nod,int st,int dr,int poz,int val)
{
    if(st==dr)
    {
        arb[nod]=min(arb[nod],val);
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        update(nod*2,st,mij,poz,val);
    else
        update(nod*2+1,mij+1,dr,poz,val);
    arb[nod]=min(arb[nod*2],arb[nod*2+1]);
}
int query(int nod,int st,int dr,int a,int b)
{
    if(st>=a&&dr<=b)
        return arb[nod];
    int rez=INF;
    int mij=(st+dr)/2;
    if(a<=mij)
        rez=min(rez,query(nod*2,st,mij,a,b));
    if(b>mij)
        rez=min(rez,query(nod*2+1,mij+1,dr,a,b));
    return rez;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int maxim=0;
    cin>>n;
    vector<int> myz;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].z;
        maxim=max(maxim,v[i].x);
        maxim=max(maxim,v[i].y);
        maxim=max(maxim,v[i].z);
        myz.push_back(v[i].z);
    }
    sort(myz.begin(),myz.end());
    myz.erase(unique(myz.begin(),myz.end()),myz.end());
    for(int i=0;i<myz.size();i++)
        nrm[myz[i]]=i+1;
    nrz=myz.size();
    int ans=-1;
    sort(v+1,v+n+1,byx);
    vector<pii> vals;
    for(int i=1;i<=n;i++)
    {
        pii x={v[i].y,v[i].z};
        if(pozmin.count(x)==0)
        {
            pozmin[x]=i;
            vals.push_back(x);
        }
    }
    sort(vals.begin(),vals.end(),byz);
    build(1,1,n);
    for(int i=0;i<vals.size();i++)
    {
        int j=i;
        vector<pii> a;
        while(j<vals.size()&&vals[j].second==vals[i].second)
        {
            a.push_back(vals[j]);
            j++;
        }
        for(pii p:a)
        {
            int y=p.first;
            int st=1;
            int dr=n;
            int poz=INF;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(query(1,1,n,1,mij)<y)
                {
                    poz=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
            poz=max(poz,pozmin[p]);
            if(poz<=n)
                enable[poz].push_back(p);
        }
        for(pii p:a)
        {
            int poz=pozmin[p];
            update(1,1,n,poz,p.first);
        }
        i=j-1;
    }
    build(1,1,nrz);
    pii ymax={-INF,INF};
    for(int i=1;i<=n;i++)
    {
        vector<point> a;
        int j=i;
        while(j<=n&&v[j].x==v[i].x)
        {
            a.push_back(v[j]);
            j++;
        }
        for(point p:a)
        {
            if(ymax.first<=p.y)
                continue;
            int poz=nrm[ymax.second];
            int st=poz+1;
            int dr=nrz;
            int best=poz;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(query(1,1,nrz,mij,nrz)<ymax.first)
                {
                    best=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            int z=myz[best-1];
            if(z>p.z)
                ans=max(ans,p.x+ymax.first+z);
        }
        j--;
        for(int k=i;k<=j;k++)
        {
            int poz=nrm[v[k].z];
            update(1,1,nrz,poz,v[k].y);
            for(pii p:enable[k])
            {
                if(p.first>ymax.first||(p.first==ymax.first&&p.second<ymax.second))
                    ymax=p;
            }
        }
        i=j;
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0;i<myz.size();i++)
      |                 ~^~~~~~~~~~~
team.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<vals.size();i++)
      |                 ~^~~~~~~~~~~~
team.cpp:106:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         while(j<vals.size()&&vals[j].second==vals[i].second)
      |               ~^~~~~~~~~~~~

• 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