Submission #1281178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281178		denislav	Team Contest (JOI22_team)	C++20	55 / 100	2095 ms	4388 KiB

team

# include <iostream>
# include <vector>
# include <algorithm>
# include <set>
using namespace std;

const int MAX=2e5+11;

int n,q;
struct point
{
    int x,y,z;
}a[MAX];
bool cmpX(point A, point B)
{
    return A.x<B.x;
}
bool cmpY(point A, point B)
{
    return A.y<B.y;
}
bool cmpZ(point A, point B)
{
    return A.z<B.z;
}

int nY,nZ;
int realY[MAX];
int realZ[MAX];

struct segtree
{
    int N;
    int tree[MAX*4];

    void build(int v, int l, int r)
    {
        if(l==r)
        {
            tree[v]=0;
            return ;
        }

        int mid=(l+r)/2;
        build(v*2,l,mid);
        build(v*2+1,mid+1,r);
        tree[v]=max(tree[v*2],tree[v*2+1]);
    }

    void init(int _N)
    {
        N=_N;
        build(1,1,N);
    }

    void update(int pos, int d, int v, int l, int r)
    {
        if(l==r)
        {
            tree[v]=max(tree[v],d);
            return ;
        }

        int mid=(l+r)/2;
        if(pos<=mid) update(pos,d,v*2,l,mid);
        else update(pos,d,v*2+1,mid+1,r);
        tree[v]=max(tree[v*2],tree[v*2+1]);
    }

    void update(int pos, int d)
    {
        update(pos,d,1,1,N);
    }

    int query(int le, int ri, int v, int l, int r)
    {
        if(ri<l or r<le) return 0;
        if(le<=l and r<=ri) return tree[v];

        int mid=(l+r)/2;
        return max(query(le,ri,v*2,l,mid),query(le,ri,v*2+1,mid+1,r));
    }

    int query(int le, int ri)
    {
        return query(le,ri,1,1,N);
    }

}treeY,treeZ;

set<pair<int,int>> bst;

void add(pair<int,int> pa)
{
    if(bst.find(pa)!=bst.end()) return ;

    vector<pair<int,int>> toRem;
    bool toAdd=1;
    bst.insert(pa);
    auto it=bst.find(pa);
    auto itL=it;
    while(itL!=bst.begin())
    {
        itL--;
        if(itL->second<=pa.second) toRem.push_back(*itL);
    }

    auto itR=it;
    if(itR!=(--bst.end()))
    {
        itR++;
        if(itR->second>=pa.second) toAdd=0;
    }

    //for(pair<int,int> pa: toRem) tree.rem(pa.first,pa.second);
    //if(toAdd) tree.add(pa.first,pa.second);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].z;
    sort(a+1,a+n+1,cmpX);

    vector<pair<int,int>> temp;
    for(int i=1;i<=n;i++) temp.push_back({a[i].y,i});
    sort(temp.begin(),temp.end());
    int last=-1;
    for(pair<int,int> pa: temp)
    {
        if(pa.first!=last)
        {
            last=pa.first;
            nY++;
            realY[nY]=last;
        }
        a[pa.second].y=nY;
    }
    temp.clear();
    for(int i=1;i<=n;i++) temp.push_back({a[i].z,i});
    sort(temp.begin(),temp.end());
    last=-1;
    for(pair<int,int> pa: temp)
    {
        if(pa.first!=last)
        {
            last=pa.first;
            nZ++;
            realZ[nZ]=last;
        }
        a[pa.second].z=nZ;
    }

    treeY.init(nY);
    treeZ.init(nZ);
    int ptr=1,ans=-1;
    for(int i=1;i<=n;i++)
    {
        while(a[ptr].x<a[i].x)
        {
            if(a[ptr].y!=1)
            {
                int z=treeY.query(1,a[ptr].y-1);
                if(z>a[ptr].z)
                add({a[ptr].y,z});
            }
            if(a[ptr].z!=1)
            {
                int y=treeZ.query(1,a[ptr].z-1);
                if(y>a[ptr].y) add({y,a[ptr].z});
            }
            treeY.update(a[ptr].y,a[ptr].z);
            treeZ.update(a[ptr].z,a[ptr].y);
            ptr++;
        }

        for(pair<int,int> pa: bst)
        {
            if(pa.first>a[i].y and pa.second>a[i].z) ans=max(ans,a[i].x+realY[pa.first]+realZ[pa.second]);
        }
    }

    cout<<ans<<"\n";

    return 0;
}

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