JOI2014春day1-historical
わからん
subtask2 imos
subtask3 しゃくとり(よい実装方法がよくわからん)
subtask4 わからん(強い人が平方分割とか言ってた、強い人に聞いてください)
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <algorithm> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define ALL(c) (c).begin(),(c).end() typedef long long ll; typedef pair<ll,ll> P; typedef pair<P,int> PP; ll anss[100000],x[100000],y[100000],naiyo[100000],imos[5000][5001]; //種類,~まで vector<ll> vc; vector<P> vv; vector<PP> vvc; set<P> st; int main(){ int n,q; scanf("%d%d",&n,&q); rep(i,n){ scanf("%lld",&x[i]); vc.push_back(x[i]); } sort(ALL(vc)); vc.erase(unique(ALL(vc)),vc.end()); if(n<=5000){ rep(i,n){ imos[lower_bound(ALL(vc),x[i])-vc.begin()][i+1]++; } rep(j,vc.size()){ rep(i,n) imos[j][i+1]+=imos[j][i]; } rep(i,q){ ll a,b; scanf("%lld%lld",&a,&b); ll ans=0; rep(j,vc.size()){ ans=max(ans,(imos[j][b]-imos[j][a-1])*vc[j]); } cout << ans << endl; } return 0; }else{ rep(i,q){ ll a,b; scanf("%lld%lld",&a,&b); vv.push_back(P(a,b)); vvc.push_back(PP(P(a,b),i)); } sort(ALL(vv)); sort(ALL(vvc)); rep(i,n){ y[i]=lower_bound(ALL(vc),x[i])-vc.begin(); //圧縮後y } ll right=0,left=0; rep(i,vv.size()){ //st:(重要度,内容(圧)) ll a=vv[i].first,b=vv[i].second; while(right!=b){ if(naiyo[y[right]]==0){ st.insert(P(x[right],y[right])); }else{ st.erase(P(naiyo[y[right]],y[right])); st.insert(P(naiyo[y[right]]+x[right],y[right])); } naiyo[y[right]]+=x[right]; right++; } while(left!=a-1){ st.erase(P(naiyo[y[left]],y[left])); st.insert(P(naiyo[y[left]]-x[left],y[left])); naiyo[y[left]]-=x[left]; left++; } set<P>::iterator it=st.end(); it--; anss[vvc[i].second]=(*it).first; } rep(i,q) printf("%lld\n",anss[i]); } return 0; }