Submission #430517

#	Time	Username	Problem	Language	Result	Execution time	Memory
430517		kimbj0709	역사적 조사 (JOI14_historical)	C++14	40 / 100	4009 ms	13752 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<int> seg(maxn*4,0);
vector<int> num(maxn,0);
vector<int> compress;
vector<int> vect1;
vector<int> ans(maxn,0);
vector<vector<pair<int,pair<int,int> > > > queries(sqrtn);
void build(int node,int start,int end){
  if(start==end){
    seg[node] = start;
    return;
  }
  int mid = (start+end)/2;
  build(node*2+1,start,mid);build(node*2+2,mid+1,end);
  seg[node] = seg[node*2+1];
}
void update(int node,int start,int end,int pos,int val){
  if(start==end){
    num[start] += val;
    return;
  }
  int mid = (start+end)/2;
  if(pos<=mid){
    update(node*2+1,start,mid,pos,val);
  }
  else{
    update(node*2+2,mid+1,end,pos,val);
  }
  if(num[seg[node*2+1]]>=num[seg[node*2+2]]){
    seg[node] = seg[node*2+1];
  }
  else{
    seg[node] = seg[node*2+2];
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int n,m;
  int input;
  cin >> n >> m;
  for(int i=0;i<n;i++){
    cin >> input;
    compress.push_back(input);
    vect1.push_back(input);
  }
  build(0,0,n-1);
  sort(compress.begin(),compress.end());
  for(int i=0;i<n;i++){
    vect1[i] = lower_bound(compress.begin(),compress.end(),vect1[i])-compress.begin();
  }
  int a,b;
  for(int i=0;i<m;i++){
    cin >> a >> b;
    a--,b--;
    queries[a/sqrtn].push_back({b,{a,i}});
  }
  int l = 0,r = -1;
  for(int i=0;i<sqrtn;i++){
    sort(queries[i].begin(),queries[i].end());
    for(auto k:queries[i]){
      while(l>k.s.f){
        l--;
        update(0,0,n-1,vect1[l],compress[vect1[l]]);
      }
      while(l<k.s.f){
        update(0,0,n-1,vect1[l],-compress[vect1[l]]);
        l++;
      }
      while(r<k.f){
        r++;
        update(0,0,n-1,vect1[r],compress[vect1[r]]);
      }
      while(r>k.f){
        update(0,0,n-1,vect1[r],-compress[vect1[r]]);
        r--;
      }
      ans[k.s.s] = num[seg[0]];
    }
  }
  for(int i=0;i<m;i++){
    cout << ans[i] << "\n";
  }

}

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