oj.uz

Submission #933104

# Submission time Handle Problem Language Result Execution time Memory
933104 2024-02-25T04:09:32 Z sleepntsheep Schools (IZhO13_school) C++17
25 / 100
 411 ms 36520 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 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

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;
      |                                                  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Incorrect 1 ms 8540 KB Output isn't correct
5 Correct 1 ms 8540 KB Output is correct
6 Incorrect 1 ms 8540 KB Output isn't correct
7 Incorrect 4 ms 9052 KB Output isn't correct
8 Incorrect 4 ms 9052 KB Output isn't correct
9 Incorrect 4 ms 9052 KB Output isn't correct
10 Incorrect 4 ms 8844 KB Output isn't correct
11 Incorrect 5 ms 9052 KB Output isn't correct
12 Incorrect 5 ms 9052 KB Output isn't correct
13 Incorrect 23 ms 11996 KB Output isn't correct
14 Incorrect 63 ms 15912 KB Output isn't correct
15 Correct 129 ms 23632 KB Output is correct
16 Incorrect 324 ms 25428 KB Output isn't correct
17 Incorrect 315 ms 29112 KB Output isn't correct
18 Incorrect 274 ms 31196 KB Output isn't correct
19 Incorrect 350 ms 32852 KB Output isn't correct
20 Incorrect 411 ms 36520 KB Output isn't correct