Submission #933104

#TimeUsernameProblemLanguageResultExecution timeMemory
933104sleepntsheepSchools (IZhO13_school)C++17
25 / 100
411 ms36520 KiB
#include<stdio.h> #include<utility> #include<set> int hi(int a,int b){return a>b?a:b;} unsigned X=12345;int rand_(){return(X*=3)/2;} int (*compar)(int,int); void sort(int*aa,int l,int r){ while(l<r){int i=l,j=l,k=r,tmp,p=aa[l+rand_()%(r-l)]; while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:tmp=aa[j],aa[j]=aa[i],aa[i]=tmp,++i,++j;break;case 1:tmp=aa[--k],aa[k]=aa[j],aa[j]=tmp;break;}sort(aa,l,i);l=k;}} #define N 500005 int nm,n,m,s,o[N],o2[N],a[N],b[N],f[N];long long z,lazy; int bya(int i,int j){return a[i]<a[j]?1:a[i]>a[j]?-1:0;} std::multiset<std::pair<int,int>>cm,cf,im,is,cf_nm; int inm(int i) { return im.find({a[o[i]],i})!=im.end(); } int ins(int i) { return is.find({b[o[i]],i})!=is.end(); } int main(){ scanf("%d%d%d",&n,&m,&s);for(int i=0;i<n;++i)scanf("%d%d",a+i,b+i),o[i]=i,o2[i]=i; compar=bya;sort(o,0,n); for(int i=0;i<m;++i)cm.insert({b[o[i]]-a[o[i]],i}),im.insert({a[o[i]],i}); for(int i=m;i<n;++i)cf.insert({b[o[i]],i}), cf_nm.insert({a[o[i]],i}); nm=m; for(;is.size()<s;) { while(nm+1<n&&(inm(nm)||ins(nm)))++nm; if(cm.empty()||(cf.size()&&cf.rbegin()->first>=cm.rbegin()->first+cf_nm.rbegin()->first)) { is.insert(*cf.rbegin()); int i=cf.rbegin()->second; cf_nm.erase({a[o[i]],i}); cf.erase(std::prev(cf.end())); } else { int i=cm.rbegin()->second; is.insert({b[o[i]],i}); cm.erase(std::prev(cm.end())); im.erase(im.find({a[o[i]],i})); int nm=cf_nm.rbegin()->second; im.insert({a[o[nm]],nm}); cm.insert({b[o[nm]]-a[o[nm]],nm}); cf_nm.erase(--cf_nm.end()); } } for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x; printf("%lld",z); }

Compilation message (stderr)

school.cpp: In function 'void sort(int*, int, int)':
school.cpp:9:8: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
    9 |        while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:tmp=aa[j],aa[j]=aa[i],aa[i]=tmp,++i,++j;break;case 1:tmp=aa[--k],aa[k]=aa[j],aa[j]=tmp;break;}sort(aa,l,i);l=k;}}
      |        ^~~~~
school.cpp:9:161: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
    9 |        while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:tmp=aa[j],aa[j]=aa[i],aa[i]=tmp,++i,++j;break;case 1:tmp=aa[--k],aa[k]=aa[j],aa[j]=tmp;break;}sort(aa,l,i);l=k;}}
      |                                                                                                                                                                 ^~~~
school.cpp: In function 'int main()':
school.cpp:35:19: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     for(;is.size()<s;)
      |          ~~~~~~~~~^~
school.cpp:61:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   61 |     for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
      |     ^~~
school.cpp:61:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   61 |     for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
      |                           ^~~
school.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d%d%d",&n,&m,&s);for(int i=0;i<n;++i)scanf("%d%d",a+i,b+i),o[i]=i,o2[i]=i;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
school.cpp:27:55: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d%d%d",&n,&m,&s);for(int i=0;i<n;++i)scanf("%d%d",a+i,b+i),o[i]=i,o2[i]=i;
      |                                                  ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...