Submission #966280

#	Time	Username	Problem	Language	Result	Execution time	Memory
966280		Trisanu_Das	Examination (JOI19_examination)	C++17	0 / 100	3086 ms	7200 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define N 100005
 
int n, q, BIT[N], ans[N], cutoffs[N][3];
vector<pair<int, int> > a;
 
void upd(int idx, int val){
  for(; idx < N; idx += (idx & -idx)) BIT[idx] += val;
}
 
int qry(int idx){
  int ans = 0;
  for(; idx >= 0; idx -= (idx & -idx)) ans += BIT[idx];
  return ans;
}
 
int sum(int l, int r){
  if(l > r) return 0;
  return qry(r) - qry(l - 1);
}
 
bool cmp(pair<int, int> a, pair<int, int> b){
  if(a == b) return 0;
  if(a.ff + a.ss > b.ff + b.ss) return 0;
  if(a.ff + a.ss < b.ff + b.ss) return 1;
  if(a.ff < b.ff) return 0;
  return 1;
  
}
 
int main(){
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  cin >> n >> q;
  for(int i = 0; i < n; i++){
    int s, t; cin >> s >> t;
    a.pb({s, t});
  }
  sort(a.begin(), a.end());
  vector<pair<pair<int, int>, int> > c_sort1;
  for(int i = 0; i < q; i++){
    cin >> cutoffs[i][0] >> cutoffs[i][1] >> cutoffs[i][2];
    if(cutoffs[i][0] + cutoffs[i][1] >= cutoffs[i][2]) c_sort1.pb({{cutoffs[i][0], cutoffs[i][1]}, i});
  }
  sort(c_sort1.begin(), c_sort1.end());
  memset(BIT, 0, sizeof(BIT));
  int idx = n - 1;
  while(!c_sort1.empty()){
    auto x = c_sort1.back(); c_sort1.pop_back();
    while(idx >= 0 && a[idx].ff >= x.ff.ff){
      upd(a[idx].ss, 1); idx--;
    }
    ans[x.ss] = sum(x.ff.ss, N - 1);
  }
  
  vector<pair<int, int> > c_sort2;
  for(int i = 0; i < q; i++)
    if(cutoffs[i][0] + cutoffs[i][1] < cutoffs[i][2]) 
      c_sort2.pb({cutoffs[i][2], i});
  
  memset(BIT, 0, sizeof(BIT));
  sort(c_sort2.begin(), c_sort2.end());
  sort(a.begin(), a.end(), cmp);
  idx = n - 1;
  for(int i = c_sort2.size() - 1; i >= 0; i--){
    while(idx >= 0 && a[idx].ff + a[idx].ss >= c_sort2[i].ff){
      upd(a[idx].ff, 1); idx--;
    }
    ans[c_sort2[i].ss] = n - idx - 1 - sum(0, cutoffs[c_sort2[i].ss][0] - 1);
  }
  memset(BIT, 0, sizeof(BIT));
  idx = n - 1;
  for(int i = c_sort2.size() - 1; i >= 0; i--){
    while(idx >= 0 && a[idx].ff + a[idx].ss >= c_sort2[i].ff){
      upd(a[idx].ss, 1); idx--;
    }
    ans[c_sort2[i].ss] -= sum(0, cutoffs[c_sort2[i].ss][0] - 1);
  }
  for(auto res : ans) cout << res << '\n';
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57