제출 #107876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107876		shoemakerjo	Examination (JOI19_examination)	C++14	2 / 100	2544 ms	1049600 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;
int n, q;
const int bil = 1000000000;
#define pii pair<int, int>
#define pp pair<int, pii>
#define mp make_pair

struct bnode {
  int count;
  bnode *left, *right;
  bnode (int count, bnode *left, bnode *right) :
    count(count), left(left), right(right) {}

  bnode* insert(int ss, int se, int bval);

  int query(int ss, int se, int bval); //want all >=
};

bnode *bnull = new bnode(0, NULL, NULL);

struct anode {
  bnode *ab;
  anode *left, *right;
  anode (bnode *ab, anode *left, anode *right) :
    ab(ab), left(left), right(right) {}

  anode *insert(int ss, int se, int aval, int bval);

  int query(int ss, int se, int aval, int bval);
};

anode *anull = new anode(NULL, NULL, NULL);

bnode * bnode::insert(int ss, int se, int bval) {
  if (ss <= bval && bval <= se) {
    if (ss == se) {
      return new bnode(this->count+1, bnull, bnull);
    }
    int mid = (ss+se)/2;
    return new bnode(this->count+1,
      this->left->insert(ss, mid, bval),
      this->right->insert(mid+1, se, bval));
  }
  return this;
}

anode * anode::insert(int ss, int se, int aval, int bval) {
  if (ss <= aval && aval <= se) {
    if (ss == se) {
      return new anode(this->ab->insert(0, bil, bval),
        anull, anull);
    }
    int mid = (ss+se)/2;
    return new anode(this->ab->insert(0, bil, bval),
      this->left->insert(ss, mid, aval, bval),
      this->right->insert(mid+1, se, aval, bval));
  }
  return this;
}

int bnode::query(int ss, int se, int bval) {
  if (bval > se) return 0;
  if (ss >= bval) {
    return this->count;
  }
  int mid = (ss+se)/2;
  return this->left->query(ss, mid, bval) +
    this->right->query(mid+1, se, bval);
}

int anode::query(int ss, int se, int aval, int bval) {
  if (aval > se) return 0;
  if (ss >= aval) {
    return this->ab->query(0, bil, bval);
  }
  int mid = (ss+se)/2;
  return this->left->query(ss, mid, aval, bval) +
    this->right->query(mid+1, se, aval, bval);
}

anode *roots[maxn];

vector<pp> vals;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  bnull->left = bnull;
  bnull->right = bnull;
  anull->ab = bnull;
  anull->left = anull;
  anull->right = anull;
  cin >> n >> q;
  int av, bv;
  for (int i = 0; i < n; i++) {
    cin >> av >> bv;
    vals.push_back(mp(av+bv, mp(av, bv)));
  }
  sort(vals.begin(), vals.end());

  roots[0] = anull;
  for (int i = 1; i <= n; i++) {
    av = vals[i-1].second.first;
    bv = vals[i-1].second.second;
    roots[i] = roots[i-1]->insert(0, bil, av, bv);
  }

  int xi, yi, zi;
  while (q--) {
    cin >> xi >> yi >> zi;
    pp tempo = mp(zi, mp(-1, -1));
    //want first with this sum
    int indo = lower_bound(vals.begin(), vals.end(), tempo) - vals.begin();
    //now it signifies what to subtract
    int res = roots[n]->query(0, bil, xi, yi) -
      roots[indo]->query(0, bil, xi, yi);

    cout << res << '\n';

  }

  cout.flush();
}

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