Submission #1274789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274789		uzukishinobu	역사적 조사 (JOI14_historical)	C++20	100 / 100	121 ms	8020 KiB

historic

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int z[1000005];
vector <int> v;
int cnt[1000005];
int res[1000005];
struct node{
     int l,r,id;
};
vector <node> q[100005];
bool cmp(node a,node b){
    return a.r<b.r;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         cin >> z[i];
         v.push_back(z[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for (int i=1;i<=a;i++){
         z[i]=lower_bound(v.begin(),v.end(),z[i])-v.begin();
    }
    int block=sqrt(a);

    for (int i=1;i<=b;i++){
         int x,y;
         cin >> x >> y;
         if (x/block==y/block){
//             cout << x  << " " <<  y << " " << cnt[1]  << "\n";
             int max1=0;
             for (int j=x;j<=y;j++){
                  cnt[z[j]]++;
                  max1=max(max1,cnt[z[j]]*v[z[j]]);
             }
             for (int j=x;j<=y;j++){
                  cnt[z[j]]--;
             }
             res[i]=max1;
         }else{
             q[x/block].push_back({x,y,i});
         }
    }
    for (int i=0;i<=a;i++){
         sort(q[i].begin(),q[i].end(),cmp);
    }
    for (int j=0;j*block<=a;j++){
         int r=(j+1)*block;
         int max1=0;
         for (auto [u,v1,id]:q[j]){
              while (r<=a && r<=v1){
                   cnt[z[r]]++;
                   max1=max(max1,v[z[r]]*cnt[z[r]]);
                   r++;
              }
              res[id]=max1;
              for (int i=u;i<(j+1)*block;i++){
                  cnt[z[i]]++;
                  res[id]=max(res[id],cnt[z[i]]*v[z[i]]);
              }
              for (int i=u;i<(j+1)*block;i++){
                  cnt[z[i]]--;
              }
         }
         for (int i=0;i<v.size();i++){
              cnt[i]=0;
         }
    }
    for (int i=1;i<=b;i++){
         cout << res[i] << "\n";
    }
    return 0;
}

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