oj.uz

Submission #370874

# Submission time Handle Problem Language Result Execution time Memory
370874 2021-02-24T21:40:49 Z kimbj0709 Examination (JOI19_examination) C++14
100 / 100
 825 ms 54896 KB 
#include <bits/stdc++.h>
using namespace std;
#define maxn 400050
#define f first
#define s second
void updatee(int b,int c,vector<int> &fenwick){
  int temp = b+1;
  //cout << "YES" << endl;
  while(temp<fenwick.size()){
    fenwick[temp] += c;
    temp += temp & (-temp);
  }
}
int getsum(int a,int b,vector<int> &fenwick){
  int temp = b+1;
  int total = 0;
  while(temp!=0){
    total += fenwick[temp];
    temp -= temp & (-temp);
  }
  int idk = a;
  while(idk!=0){
    total -= fenwick[idk];
    idk -= idk & (-idk);
  }
  return total;
}
vector<pair<int,int> > nums;
vector<vector<int> > vals(maxn);
vector<vector<int> > segs(maxn);
void build(int node,int start,int end){
  for(int i=start;i<=end;i++){
    vals[node].push_back(nums[i].s);
    segs[node].push_back(0);
  }
  segs[node].push_back(0);
  sort(vals[node].begin(),vals[node].end());
  if(start==end){
    return;
  }
  int mid = (start+end)/2;
  build(node*2+1,start,mid);
  build(node*2+2,mid+1,end);
}
void update(int node,int start,int end,int val1,int val2){
  int pos = lower_bound(vals[node].begin(),vals[node].end(),val2)-vals[node].begin();
  updatee(pos,1,segs[node]);
  assert(vals[node][pos]==val2);
  if(start==end){
    return;
  }
  int mid = (start+end)/2;
  if((val1<nums[mid].f)||(val1==nums[mid].f&&val2<=nums[mid].s)){
    update(node*2+1,start,mid,val1,val2);
  }
  else{
    update(node*2+2,mid+1,end,val1,val2);
  }
}
int query(int node,int start,int end,int val1,int val2){
  if(nums[end].f<val1){
    return 0;
  }
  if(nums[start].f>=val1){
    if(val2>vals[node][vals[node].size()-1]){
      return 0;
    }
    int pos = upper_bound(vals[node].begin(),vals[node].end(),val2-1)-vals[node].begin();
    //cout << pos << " " << vals[node][pos] << " " << val2 << "--\n";
    return getsum(pos,vals[node].size()-1,segs[node]);
  }
  int mid = (start+end)/2;
  return query(node*2+1,start,mid,val1,val2)+query(node*2+2,mid+1,end,val1,val2);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int n,q;
  cin >> n >> q;
  int a,b,c;
  vector<pair<int,pair<int,int> > > vect1;
  vector<pair<int,pair<int,pair<int,int> > > > queries;
  for(int i=0;i<n;i++){
    cin >> a >> b;
    vect1.push_back({a+b,{a,b}});
    nums.push_back({a,b});
  }
  sort(nums.begin(),nums.end());
  vector<int> ans(q);
  for(int i=0;i<q;i++){
    cin >> a >> b >> c;
    queries.push_back({c,{a,{b,i}}});
  }
  build(0,0,vect1.size()-1);
  sort(vect1.begin(),vect1.end());
  sort(queries.begin(),queries.end());
  reverse(queries.begin(),queries.end());
  reverse(vect1.begin(),vect1.end());
  int currpos = 0;
  for(int i=0;i<queries.size();i++){
    while(currpos<vect1.size()&&vect1[currpos].f>=queries[i].f){
      update(0,0,vect1.size()-1,vect1[currpos].s.f,vect1[currpos].s.s);
      currpos++;
    }
    int currans = query(0,0,vect1.size()-1,queries[i].s.f,queries[i].s.s.f);
    ans[queries[i].s.s.s] = currans;
  }
  /*for(auto k:vals[1]){
    cout << k << " ";
  }
  cout << endl;*/
  for(auto k:ans){
    cout << k << '\n';
  }
}

Compilation message

examination.cpp: In function 'void updatee(int, int, std::vector<int>&)':
examination.cpp:9:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |   while(temp<fenwick.size()){
      |         ~~~~^~~~~~~~~~~~~~~
examination.cpp: In function 'int32_t main()':
examination.cpp:100:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int i=0;i<queries.size();i++){
      |               ~^~~~~~~~~~~~~~~
examination.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     while(currpos<vect1.size()&&vect1[currpos].f>=queries[i].f){
      |           ~~~~~~~^~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19200 KB Output is correct
2 Correct 14 ms 19180 KB Output is correct
3 Correct 13 ms 19180 KB Output is correct
4 Correct 13 ms 19180 KB Output is correct
5 Correct 13 ms 19180 KB Output is correct
6 Correct 13 ms 19180 KB Output is correct
7 Correct 24 ms 20096 KB Output is correct
8 Correct 24 ms 20076 KB Output is correct
9 Correct 24 ms 20076 KB Output is correct
10 Correct 22 ms 20076 KB Output is correct
11 Correct 22 ms 20076 KB Output is correct
12 Correct 20 ms 19948 KB Output is correct
13 Correct 24 ms 20076 KB Output is correct
14 Correct 23 ms 20076 KB Output is correct
15 Correct 23 ms 20076 KB Output is correct
16 Correct 20 ms 20076 KB Output is correct
17 Correct 20 ms 20096 KB Output is correct
18 Correct 19 ms 19948 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 52552 KB Output is correct
2 Correct 636 ms 52384 KB Output is correct
3 Correct 638 ms 52464 KB Output is correct
4 Correct 422 ms 51728 KB Output is correct
5 Correct 407 ms 51696 KB Output is correct
6 Correct 285 ms 50928 KB Output is correct
7 Correct 659 ms 52332 KB Output is correct
8 Correct 615 ms 52500 KB Output is correct
9 Correct 649 ms 52336 KB Output is correct
10 Correct 349 ms 51568 KB Output is correct
11 Correct 327 ms 51568 KB Output is correct
12 Correct 264 ms 50544 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 52552 KB Output is correct
2 Correct 636 ms 52384 KB Output is correct
3 Correct 638 ms 52464 KB Output is correct
4 Correct 422 ms 51728 KB Output is correct
5 Correct 407 ms 51696 KB Output is correct
6 Correct 285 ms 50928 KB Output is correct
7 Correct 659 ms 52332 KB Output is correct
8 Correct 615 ms 52500 KB Output is correct
9 Correct 649 ms 52336 KB Output is correct
10 Correct 349 ms 51568 KB Output is correct
11 Correct 327 ms 51568 KB Output is correct
12 Correct 264 ms 50544 KB Output is correct
13 Correct 797 ms 52960 KB Output is correct
14 Correct 792 ms 52968 KB Output is correct
15 Correct 639 ms 52532 KB Output is correct
16 Correct 564 ms 52080 KB Output is correct
17 Correct 493 ms 52208 KB Output is correct
18 Correct 279 ms 50964 KB Output is correct
19 Correct 821 ms 52984 KB Output is correct
20 Correct 803 ms 52848 KB Output is correct
21 Correct 792 ms 52848 KB Output is correct
22 Correct 346 ms 51568 KB Output is correct
23 Correct 322 ms 51568 KB Output is correct
24 Correct 265 ms 50544 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19200 KB Output is correct
2 Correct 14 ms 19180 KB Output is correct
3 Correct 13 ms 19180 KB Output is correct
4 Correct 13 ms 19180 KB Output is correct
5 Correct 13 ms 19180 KB Output is correct
6 Correct 13 ms 19180 KB Output is correct
7 Correct 24 ms 20096 KB Output is correct
8 Correct 24 ms 20076 KB Output is correct
9 Correct 24 ms 20076 KB Output is correct
10 Correct 22 ms 20076 KB Output is correct
11 Correct 22 ms 20076 KB Output is correct
12 Correct 20 ms 19948 KB Output is correct
13 Correct 24 ms 20076 KB Output is correct
14 Correct 23 ms 20076 KB Output is correct
15 Correct 23 ms 20076 KB Output is correct
16 Correct 20 ms 20076 KB Output is correct
17 Correct 20 ms 20096 KB Output is correct
18 Correct 19 ms 19948 KB Output is correct
19 Correct 643 ms 52552 KB Output is correct
20 Correct 636 ms 52384 KB Output is correct
21 Correct 638 ms 52464 KB Output is correct
22 Correct 422 ms 51728 KB Output is correct
23 Correct 407 ms 51696 KB Output is correct
24 Correct 285 ms 50928 KB Output is correct
25 Correct 659 ms 52332 KB Output is correct
26 Correct 615 ms 52500 KB Output is correct
27 Correct 649 ms 52336 KB Output is correct
28 Correct 349 ms 51568 KB Output is correct
29 Correct 327 ms 51568 KB Output is correct
30 Correct 264 ms 50544 KB Output is correct
31 Correct 797 ms 52960 KB Output is correct
32 Correct 792 ms 52968 KB Output is correct
33 Correct 639 ms 52532 KB Output is correct
34 Correct 564 ms 52080 KB Output is correct
35 Correct 493 ms 52208 KB Output is correct
36 Correct 279 ms 50964 KB Output is correct
37 Correct 821 ms 52984 KB Output is correct
38 Correct 803 ms 52848 KB Output is correct
39 Correct 792 ms 52848 KB Output is correct
40 Correct 346 ms 51568 KB Output is correct
41 Correct 322 ms 51568 KB Output is correct
42 Correct 265 ms 50544 KB Output is correct
43 Correct 825 ms 54816 KB Output is correct
44 Correct 803 ms 54896 KB Output is correct
45 Correct 805 ms 54768 KB Output is correct
46 Correct 594 ms 53232 KB Output is correct
47 Correct 486 ms 53360 KB Output is correct
48 Correct 279 ms 50800 KB Output is correct
49 Correct 737 ms 54728 KB Output is correct
50 Correct 754 ms 54768 KB Output is correct
51 Correct 696 ms 54568 KB Output is correct
52 Correct 370 ms 53104 KB Output is correct
53 Correct 336 ms 52336 KB Output is correct