Submission #425461

#	Time	Username	Problem	Language	Result	Execution time	Memory
425461		errorgorn	Feast (NOI19_feast)	C++17	100 / 100	171 ms	14576 KiB

feast

#include <cstdio>
#include <utility>
#include <queue>
#include <cstdlib>
using namespace std;
typedef pair<int,int> ii;
typedef pair<long long,ii> iii;
int n,m,pos;
long long t,total;
int p[300005];
int r[300005];
iii node[300005];
priority_queue<iii, vector<iii>, greater<iii> > pq;
int parent(int i){return (p[i]==i)?i: p[i]=parent(p[i]);}
void unions(int i,int j){ //update node
    i=parent(i),j=parent(j);
    if (i>j) swap(i,j);
    if (r[i]>r[j]){
        p[j]=i;
        node[i]=iii (node[i].first+node[j].first, ii(node[i].second.first,node[j].second.second));
    }
    else{
        p[i]=j;
        if (r[i]==r[j]) r[j]++;
        node[j]=iii (node[i].first+node[j].first, ii(node[i].second.first,node[j].second.second));
    }
}
void init(){
    for (int x=0;x<300005;x++){
        p[x]=x;
        r[x]=0;
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&m);
    init();
    for (int x=0;x<n;x++){
        scanf("%lld",&t);
        node[x]=iii(t, ii(x,x));
    }
    for (int x=1;x<n;x++){
        if ( node[parent(x)].first==0 || (node[parent(x-1)].first^node[parent(x)].first)>=0 ){
            unions(x-1,x);
        }
    }
    for (int x=0;x<n;){
        x=parent(x);
        if ( !( (node[x].second.first==0 || node[x].second.second==n-1)&& node[x].first<0) )pq.push(iii(llabs(node[x].first),node[x].second));
        if (node[x].first>0) pos++,total+=node[x].first;
        x=node[x].second.second+1;
    }
    //printf("%d %lld\n",pos,total);
    int s,e;
    long long v;
    while (pos>m){
        v=pq.top().first,s=pq.top().second.first,e=pq.top().second.second,pq.pop();
        if (node[parent(s)].second!=ii(s,e) ) continue;
        //printf("%d %d\n",s,e);
        pos--;
        total-=v;
        if (s!=0){
            unions(s,s-1);
        }
        if (e!=n-1){
            unions(e,e+1);
        }
         if ( !( (node[parent(s)].second.first==0 || node[parent(s)].second.second==n-1)&& node[parent(s)].first<0) ) pq.push(iii(abs(node[parent(s)].first),node[parent(s)].second));
    }
    /*for (int x=0;x<n;){
        x=parent(x);
        printf("%lld %d %d\n",node[x].first,node[x].second.first,node[x].second.second);
        x=node[x].second.second+1;
    }*/
    printf("%lld\n",total);
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
feast.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%lld",&t);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29