Submission #430542

#	Time	Username	Problem	Language	Result	Execution time	Memory
430542		kimbj0709	역사적 조사 (JOI14_historical)	C++14	40 / 100	4091 ms	57076 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);
priority_queue<int> ins,del;
void insert(int node){
  //cout << node << endl;
  num[node] += compress[node];
  ins.push(num[node]);
}
void deleter(int node){
  //cout << node << endl;
  del.push(num[node]);
  num[node] -= compress[node];
}
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);
  }
  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}});
  }
  //cout << "YES" << endl;
  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--;
        insert(vect1[l]);
      }
      while(l<k.s.f){
        deleter(vect1[l]);
        l++;
      }
      while(r<k.f){
        r++;
        insert(vect1[r]);
      }
      while(r>k.f){
        deleter(vect1[r]);
        r--;
      }
      while(del.size()>0&&ins.top()==del.top()){
        ins.pop();
        del.pop();
      }
      ans[k.s.s] = ins.top();
     // cout << "YES" << endl;
    }
  }
  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