oj.uz

Submission #933103

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

signed main(){
    scanf("%lld%lld%lld",&n,&m,&s);for(int i=0;i<n;++i)scanf("%lld%lld",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(long long int*, long long int, long long int)':
school.cpp:11:8: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   11 |        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:11:161: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   11 |        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:39:19: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   39 |     for(;is.size()<s;)
      |          ~~~~~~~~~^~
school.cpp:60:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   60 |     for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
      |     ^~~
school.cpp:60:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   60 |     for(auto[x,y]:im)z+=x;for(auto[x,y]:is)z+=x;
      |                           ^~~
school.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%lld%lld%lld",&n,&m,&s);for(int i=0;i<n;++i)scanf("%lld%lld",a+i,b+i),o[i]=i,o2[i]=i;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:32:61: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%lld%lld%lld",&n,&m,&s);for(int i=0;i<n;++i)scanf("%lld%lld",a+i,b+i),o[i]=i,o2[i]=i;
      |                                                        ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Incorrect 2 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 3 ms 8796 KB Output isn't correct
8 Incorrect 3 ms 9000 KB Output isn't correct
9 Incorrect 4 ms 9052 KB Output isn't correct
10 Incorrect 5 ms 9052 KB Output isn't correct
11 Incorrect 5 ms 9304 KB Output isn't correct
12 Incorrect 5 ms 8796 KB Output isn't correct
13 Incorrect 22 ms 12808 KB Output isn't correct
14 Incorrect 50 ms 14036 KB Output isn't correct
15 Correct 89 ms 18436 KB Output is correct
16 Incorrect 187 ms 24404 KB Output isn't correct
17 Incorrect 259 ms 35308 KB Output isn't correct
18 Incorrect 210 ms 38592 KB Output isn't correct
19 Incorrect 264 ms 40100 KB Output isn't correct
20 Incorrect 285 ms 42832 KB Output isn't correct