Submission #1182708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182708		sleepntsheep	역사적 조사 (JOI14_historical)	C++17	5 / 100	1 ms	1040 KiB

historic

#include<stdio.h>
#include<string.h>
#include<algorithm>

int n,nq,x[100000],cr,bb[100000],xs[100000],freq[100000];
long long ans[100000],mx;
struct QUERY{
    int l,r,i;
    bool operator<(const QUERY&o)const{
        if(bb[l]!=bb[o.l])return l<o.l;
        return r<o.r;
    }
}q[100000];

int main(){
    scanf("%d%d",&n,&nq);
    for(int i=0;i<n;++i)scanf("%d",&x[i]),bb[i]=i/500,xs[i]=x[i];
    std::sort(xs,xs+n);
    for(int i=0;i<n;++i)x[i]=std::lower_bound(xs,xs+n,x[i])-xs;
    for(int i=0;i<nq;++i)scanf("%d%d",&q[i].l,&q[i].r),q[i].i=i,--q[i].l,--q[i].r;
    std::sort(q,q+nq);

    for(int i=0;i<nq;++i){
        auto&[l,r,i_]=q[i];
        if(!i||bb[l]!=bb[q[i-1].l]){
            memset(freq,0,sizeof freq);
            cr=0;
            mx=0;
        }
        while(cr<r){
            if(bb[cr]>bb[l]){
                ++freq[x[cr]];
                if(freq[x[cr]]*1ll*xs[x[cr]]>mx)
                    mx=1ll*freq[x[cr]]*xs[x[cr]];
            }
            ++cr;
        }

        long long mx_=mx;
        for(int j=l;j<=cr&&bb[l]==bb[j];++j){
            ++freq[x[j]];
            if(freq[x[j]]*1ll*xs[x[j]]>mx_)
                mx_=1ll*freq[x[j]]*xs[x[j]];
        }

        for(int j=l;j<=cr&&bb[l]==bb[j];++j)
            --freq[x[j]];
        ans[i_]=mx_;
    }

    for(int i=0;i<nq;++i)printf("%lld\n",ans[i]);

    return 0;
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d",&n,&nq);
      |     ~~~~~^~~~~~~~~~~~~~~
historic.cpp:17:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     for(int i=0;i<n;++i)scanf("%d",&x[i]),bb[i]=i/500,xs[i]=x[i];
      |                         ~~~~~^~~~~~~~~~~~
historic.cpp:20:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     for(int i=0;i<nq;++i)scanf("%d%d",&q[i].l,&q[i].r),q[i].i=i,--q[i].l,--q[i].r;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60