oj.uz

Submission #933105

# Submission time Handle Problem Language Result Execution time Memory
933105 2024-02-25T04:17:41 Z sleepntsheep Schools (IZhO13_school) C++17
100 / 100
 446 ms 36436 KB 
#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 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::set<std::pair<int,int>>cm,cf,im,is,cf_nm;

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});

    for(;is.size()<s;)
    {
        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({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.erase({b[o[nm]],nm});
            cf_nm.erase(std::prev(cf_nm.end()));
        }
    }

    for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
    printf("%lld",z);
}

Compilation message

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:24:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     for(;is.size()<s;)
      |          ~~~~~~~~~^~
school.cpp:49:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   49 |     for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
      |     ^~~
school.cpp:49:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   49 |     for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
      |                           ^~~
school.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     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:18:55: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     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;
      |                                                  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 4 ms 8796 KB Output is correct
8 Correct 4 ms 9052 KB Output is correct
9 Correct 4 ms 9052 KB Output is correct
10 Correct 4 ms 9052 KB Output is correct
11 Correct 5 ms 9052 KB Output is correct
12 Correct 5 ms 9108 KB Output is correct
13 Correct 23 ms 11772 KB Output is correct
14 Correct 61 ms 15696 KB Output is correct
15 Correct 132 ms 23376 KB Output is correct
16 Correct 368 ms 25424 KB Output is correct
17 Correct 286 ms 29144 KB Output is correct
18 Correct 294 ms 31192 KB Output is correct
19 Correct 367 ms 32940 KB Output is correct
20 Correct 446 ms 36436 KB Output is correct