Submission #431591

#	Time	Username	Problem	Language	Result	Execution time	Memory
431591		kimbj0709	역사적 조사 (JOI14_historical)	C++14	100 / 100	752 ms	11444 KiB

historic

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
#define sqrtn 320
#define f first
#define s second
vector<vector<pair<int,pair<int,int> > > > queries(sqrtn);
vector<int> cnt(maxn,0);
vector<int> ans(maxn,0);
vector<int> isspecial(maxn,0);
vector<int> vect1;
vector<int> compress;
int currmx = 0;
void rem(int a){
  cnt[a]--;
}
void add(int a){
  cnt[a]++;
  if(isspecial[a]==0){
    currmx = max(currmx,cnt[a]*compress[a]);
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int n,m;
  cin >> n >> m;
  int input,a,b;
  for(int i=0;i<n;i++){
    cin >> input;
    vect1.push_back(input);
    compress.push_back(input);
  }
  sort(compress.begin(),compress.end());
  for(int i=0;i<n;i++){
    vect1[i] = lower_bound(compress.begin(),compress.end(),vect1[i])-compress.begin();
  }
  for(int i=0;i<m;i++){
    cin >> a >> b;
    a--,b--;
    queries[a/sqrtn].push_back({b,{a,i}});
  }
  for(int i=0;i<sqrtn;i++){
    sort(queries[i].begin(),queries[i].end());
    if(queries[i].size()==0){
      continue;
    }
    for(int j=0;j<maxn;j++){
      cnt[j] = 0;
      isspecial[j] = 0;
    }
    currmx = 0;
    int currpos = (i+1)*sqrtn-1;
    int l = 0,r = -1;
    for(int j=sqrtn*i;j<=min(n-1,currpos);j++){
      isspecial[vect1[j]] = 1;
    }
    for(int j=0;j<=min(n-1,currpos);j++){
      rem(vect1[j]);
    }
    for(auto k:queries[i]){
      for(int j=k.s.f;j<=min(n-1,currpos);j++){
        add(vect1[j]);
      }
      while(r<k.f){
        r++;
        add(vect1[r]);
      }
      int currans = currmx;
      for(int j=i*sqrtn;j<=min(n-1,currpos);j++){
        currans = max(currans,cnt[vect1[j]]*compress[vect1[j]]);
      }
      ans[k.s.s] = currans;
      for(int j=k.s.f;j<=min(n-1,currpos);j++){
        rem(vect1[j]);
      }
    }
  }
  for(int i=0;i<m;i++){
    cout << ans[i] << "\n";
  }
  
}

Compilation message (stderr)

historic.cpp: In function 'int32_t main()':
historic.cpp:55:9: warning: unused variable 'l' [-Wunused-variable]
   55 |     int l = 0,r = -1;
      |         ^

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