oj.uz

Submission #486036

# Submission time Handle Problem Language Result Execution time Memory
486036 2021-11-10T11:47:37 Z urd05 역사적 조사 (JOI14_historical) C++17
0 / 100
 5 ms 5196 KB 
#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;

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++) {
                hubo.push_back(arr[j]);
            }
        }
        else {
            while (l%sq!=0) {
                hubo.push_back(arr[l]);
                l++;
            }
            while (r%sq!=sq-1) {
                hubo.push_back(arr[r]);
                r--;
            }
            if (l/sq<=r/sq)
                hubo.push_back(save[l/sq][r/sq]);
        }
        sort(hubo.begin(),hubo.end());
        hubo.erase(unique(hubo.begin(),hubo.end()));
        long long ret=0;
        for(int j=0;j<hubo.size();j++) {
            ret=max(ret,cal(hubo[j],ll,rr));
        }
        printf("%lld\n",ret);
    }
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -