Submission #486039

#	Time	Username	Problem	Language	Result	Execution time	Memory
486039		urd05	역사적 조사 (JOI14_historical)	C++17	100 / 100	3630 ms	15284 KiB

historic

#include <bits/stdc++.h>
using namespace std;
 
vector<int> press;
vector<int> vec[100000];
int n,q;
int arr[100000];
const int sq=320;
int save[320][320];
typedef pair<long long,int> P;
bool chk[100000];
 
long long cal(int x,int l,int r) {
    return press[x]*(upper_bound(vec[x].begin(),vec[x].end(),r)-lower_bound(vec[x].begin(),vec[x].end(),l));
}
 
int main(void) {
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++) {
        scanf("%d",&arr[i]);
        press.push_back(arr[i]);
    }
    sort(press.begin(),press.end());
    press.erase(unique(press.begin(),press.end()),press.end());
    for(int i=0;i<n;i++) {
        arr[i]=lower_bound(press.begin(),press.end(),arr[i])-press.begin();
        vec[arr[i]].push_back(i);
    }
    for(int i=0;i<n;i+=sq) {
        priority_queue<P> pq;
        priority_queue<P> er;
        vector<long long> temp(press.size());
        for(int j=0;j<press.size();j++) {
            pq.push(P(0,j));
            temp[j]=0;
        }
        for(int j=i;j<n;j++) {
            er.push(P(temp[arr[j]],arr[j]));
            temp[arr[j]]+=press[arr[j]];
            pq.push(P(temp[arr[j]],arr[j]));
            while (!er.empty()&&pq.top()==er.top()) {
                pq.pop();
                er.pop();
            }
            if (j%sq==sq-1) {
                save[i/sq][j/sq]=pq.top().second;
            }
        }
    }
    for(int i=0;i<q;i++) {
        int l,r;
        scanf("%d %d",&l,&r);
        l--;
        r--;
        int ll=l;
        int rr=r;
        vector<int> hubo;
        if (l/sq==r/sq) {
            for(int j=l;j<=r;j++) {
                if (!chk[arr[j]])
                hubo.push_back(arr[j]);
                chk[arr[j]]=true;
            }
        }
        else {
            while (l%sq!=0) {
                if (!chk[arr[l]])
                hubo.push_back(arr[l]);
                chk[arr[l]]=true;
                l++;
            }
            while (r%sq!=sq-1) {
                if (!chk[arr[r]])
                hubo.push_back(arr[r]);
                chk[arr[r]]=true;
                r--;
            }
            if (l/sq<=r/sq)
                hubo.push_back(save[l/sq][r/sq]);
        }
        long long ret=0;
        for(int j=0;j<hubo.size();j++) {
            ret=max(ret,cal(hubo[j],ll,rr));
            chk[hubo[j]]=false;
        }
        printf("%lld\n",ret);
    }
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int j=0;j<press.size();j++) {
      |                     ~^~~~~~~~~~~~~
historic.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int j=0;j<hubo.size();j++) {
      |                     ~^~~~~~~~~~~~
historic.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
historic.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%d",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~
historic.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d %d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~

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