oj.uz

Submission #107876

# Submission time Handle Problem Language Result Execution time Memory
107876 2019-04-26T05:39:17 Z shoemakerjo Examination (JOI19_examination) C++14
2 / 100
 2544 ms 1049600 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 199 ms 93324 KB Output is correct
8 Correct 221 ms 93460 KB Output is correct
9 Correct 260 ms 93308 KB Output is correct
10 Correct 276 ms 93560 KB Output is correct
11 Correct 234 ms 93560 KB Output is correct
12 Correct 204 ms 93660 KB Output is correct
13 Correct 218 ms 93304 KB Output is correct
14 Correct 208 ms 93360 KB Output is correct
15 Correct 222 ms 93352 KB Output is correct
16 Correct 188 ms 93560 KB Output is correct
17 Correct 163 ms 93664 KB Output is correct
18 Correct 169 ms 93688 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2544 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2544 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 199 ms 93324 KB Output is correct
8 Correct 221 ms 93460 KB Output is correct
9 Correct 260 ms 93308 KB Output is correct
10 Correct 276 ms 93560 KB Output is correct
11 Correct 234 ms 93560 KB Output is correct
12 Correct 204 ms 93660 KB Output is correct
13 Correct 218 ms 93304 KB Output is correct
14 Correct 208 ms 93360 KB Output is correct
15 Correct 222 ms 93352 KB Output is correct
16 Correct 188 ms 93560 KB Output is correct
17 Correct 163 ms 93664 KB Output is correct
18 Correct 169 ms 93688 KB Output is correct
19 Runtime error 2544 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -