Submission #278768

#	Time	Username	Problem	Language	Result	Execution time	Memory
278768		MKopchev	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	689 ms	43640 KiB

constellation3

#include<bits/stdc++.h>
using namespace std;

const int nmax=2e5+42;

vector< pair<int/*x*/,int/*gain*/> > stars[nmax];

vector< pair<int/*y*/,int/*gain*/> > seen[nmax];

bool cmp(pair<int/*y*/,int/*gain*/> a,pair<int/*y*/,int/*gain*/> b)
{
    if(a.first!=b.first)return a.first>b.first;
    return a.second<b.second;
}
int n;
int inp[nmax];

int q;

vector< int/*x*/ > white[nmax];

int prv_seen[nmax];

struct info
{
    long long lazy,mx;
};

info tree[4*nmax];

info actual(info a)
{
    a.mx+=a.lazy;
    a.lazy=0;

    return a;
}
info my_merge(info a,info b)
{
    a=actual(a);
    b=actual(b);

    a.mx=max(a.mx,b.mx);
    return a;
}

void push(int node)
{
    tree[node*2].lazy+=tree[node].lazy;
    tree[node*2+1].lazy+=tree[node].lazy;
    tree[node].lazy=0;
}

void update(int node,int l,int r,int lq,int rq,long long val)
{
    if(l==lq&&r==rq)
    {
        tree[node].lazy+=val;
        return;
    }

    push(node);

    int av=(l+r)/2;

    if(lq<=av)update(node*2,l,av,lq,min(av,rq),val);
    if(av<rq)update(node*2+1,av+1,r,max(av+1,lq),rq,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

info query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return actual(tree[node]);

    int av=(l+r)/2;

    info ret;ret.mx=0;ret.lazy=0;

    if(lq<=av)ret=my_merge(ret,query(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ret=my_merge(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));

    return ret;
}

int le[nmax],ri[nmax],parent[nmax];
int root(int node)
{
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
}

int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    for(int i=1;i<n;i++)
        white[max(inp[i],inp[i+1])].push_back(i);

    long long outp=0;

    scanf("%i",&q);
    for(int i=1;i<=q;i++)
    {
        int x,y,c;

        scanf("%i%i%i",&x,&y,&c);

        outp+=c;

        seen[x].push_back({y,c});
        //stars[y].push_back({x,c});
    }

    for(int i=1;i<=n;i++)
        if(seen[i].size())
        {
            sort(seen[i].begin(),seen[i].end(),cmp);

            vector< pair<int/*y*/,int/*gain*/> > help={};

            for(auto k:seen[i])
            {
                while(help.size()&&help.back().second<=k.second)
                {
                    //outp-=help.back().second;
                    help.pop_back();
                }

                help.push_back(k);
            }

            for(auto k:help)
            {
                stars[k.first].push_back({i,k.second});
            }
            /*
            cout<<i<<endl;
            for(auto k:seen[i])
            {
                cout<<"y= "<<k.first<<" cost= "<<k.second<<endl;
            }
            cout<<"->"<<endl;
            for(auto k:help)
            {
                cout<<"y= "<<k.first<<" cost= "<<k.second<<endl;
            }
            */
        }

    for(int i=1;i<=n;i++)
    {
        le[i]=i;
        ri[i]=i;

        parent[i]=i;
    }

    for(int i=1;i<=n;i++)
    {
        for(auto k:stars[i])
        {
            update(1,1,n,k.first,k.first,k.second-prv_seen[k.first]);
            prv_seen[k.first]=k.second;
        }

        for(auto k:white[i])
        {
            int l1=le[root(k)],r1=k;
            int l2=k+1,r2=ri[root(k+1)];

            long long mx_1=query(1,1,n,l1,r1).mx,mx_2=query(1,1,n,l2,r2).mx;

            parent[root(k+1)]=root(k);

            le[root(k)]=l1;
            ri[root(k)]=r2;

            update(1,1,n,l1,r1,mx_2);
            update(1,1,n,l2,r2,mx_1);
        }
    }

    printf("%lld\n",outp-actual(tree[1]).mx);
    return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
constellation3.cpp:97:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
      |                          ~~~~~^~~~~~~~~~~~~~
constellation3.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |     scanf("%i",&q);
      |     ~~~~~^~~~~~~~~
constellation3.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |         scanf("%i%i%i",&x,&y,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65