oj.uz

Submission #933102

# Submission time Handle Problem Language Result Execution time Memory
933102 2024-02-25T04:06:13 Z sleepntsheep Schools (IZhO13_school) C++17
25 / 100
 263 ms 31440 KB 
#include<stdio.h>
#include<utility>
#include<set>
#include<queue>
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;}

int nm;

std::multiset<std::pair<int,int>>cm,cf,im,is;
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});

    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+a[o[nm]]))
        {
            is.insert(*cf.rbegin());
            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}));

            im.insert({a[o[nm]],nm});
            cm.insert({b[o[nm]]-a[o[nm]],nm});
        }
    }

    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:10:8: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   10 |        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:10:161: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   10 |        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:38: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]
   38 |     for(;is.size()<s;)
      |          ~~~~~~~~~^~
school.cpp:59:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   59 |     for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
      |     ^~~
school.cpp:59:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   59 |     for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
      |                           ^~~
school.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     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:31:55: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     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 4 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 2 ms 8540 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 8536 KB Output isn't correct
7 Incorrect 3 ms 8796 KB Output isn't correct
8 Incorrect 3 ms 9052 KB Output isn't correct
9 Incorrect 3 ms 9052 KB Output isn't correct
10 Incorrect 4 ms 8900 KB Output isn't correct
11 Incorrect 4 ms 9156 KB Output isn't correct
12 Incorrect 4 ms 8796 KB Output isn't correct
13 Incorrect 22 ms 12036 KB Output isn't correct
14 Incorrect 46 ms 13540 KB Output isn't correct
15 Correct 85 ms 17744 KB Output is correct
16 Incorrect 186 ms 20792 KB Output isn't correct
17 Incorrect 205 ms 26448 KB Output isn't correct
18 Incorrect 209 ms 27616 KB Output isn't correct
19 Incorrect 212 ms 28928 KB Output isn't correct
20 Incorrect 263 ms 31440 KB Output isn't correct