oj.uz

Submission #401356

# Submission time Handle Problem Language Result Execution time Memory
401356 2021-05-10T01:31:07 Z erray Examination (JOI19_examination) C++11
100 / 100
 552 ms 18332 KB 
// author: erray
#include <bits/stdc++.h>
 
using namespace std;
 template<typename A, typename B> string to_string(pair<A, B> p);
template<typename A, typename B, typename C> string to_string(tuple<A, B, C> t);
template<typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> t);

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(char c) {
  return string("'") + c + "'";
}

string to_string(const char* c) {
  return to_string(string(c));
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template<size_t T> string to_string(bitset<T> bs) {
  return bs.to_string();
}

string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < int(v.size()); ++i) {
    if (i > 0) {
      res += ", ";
    }
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template<typename T> string to_string(T v) {
  string res = "{";
  for (auto& e : v) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(e);
  }
  res += "}";
  return res;
}

template<typename A, typename B> string to_string(pair<A, B> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
template<typename A, typename B, typename C> string to_string(tuple<A, B, C> t) {
  return '(' + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + '}';
}
template<typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> t) {
  return '(' + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + '}';   
}

void debug_out() {
  cerr << endl;
}

template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << "  " << to_string(H);
  debug_out(T...);
}

#ifdef DEBUG 
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) void(37)
#endif

struct Fenw {
  int n;
  vector<int> tree;

  inline int lb(int x) { return x & -x; }

  int get(int x) {
    ++x;
    int res = 0;
    while (x > 0) {
      res += tree[x];
      x -= lb(x);
    }
    return res;
  }

  void modify(int x, int add = 1) {
    ++x;
    while (x <= n) {
      tree[x] += add;
      x += lb(x);
    }
  }

  Fenw(int _n) : n(_n) {
    tree.resize(n + 1);
  }
};
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<array<int, 3>> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i][0] >> a[i][1];
    a[i][2] = a[i][0] + a[i][1];
  }

  vector<array<int, 4>> qs(q);
  for (int i = 0; i < q; ++i) {
    cin >> qs[i][0] >> qs[i][1] >> qs[i][2];
    qs[i][3] = i;
  }
  array<vector<int>, 3> all;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      all[j].push_back(a[i][j]);
    }
  }
  for (int i = 0; i < q; ++i) {
    for (int j = 0; j < 3; ++j) {
      all[j].push_back(qs[i][j]);
    }
  }
  for (int j = 0; j < 3; ++j) {
    sort(all[j].begin(), all[j].end());
    all[j].erase(unique(all[j].begin(), all[j].end()), all[j].end());
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      a[i][j] = int(lower_bound(all[j].begin(), all[j].end(), a[i][j]) - all[j].begin()); 
    }
  }
  for (int i = 0; i < q; ++i) {
    for (int j = 0; j < 3; ++j) {
      qs[i][j] = int(lower_bound(all[j].begin(), all[j].end(), qs[i][j]) - all[j].begin());
    }
  }
  debug(a);
  debug(qs);
  sort(a.rbegin(), a.rend());
  sort(qs.rbegin(), qs.rend()); 
  vector<array<int, 3>> event;
  int p = 0;
  for (int i = 0; i < n; ++i) {
    while (p < q && qs[p][0] > a[i][0]) {
      event.push_back({qs[p][1], qs[p][2], qs[p][3]});
      ++p;
    }
    event.push_back({a[i][1], a[i][2], -1});
  }
  while (p < q) {
    event.push_back({qs[p][1], qs[p][2], qs[p][3]});
    ++p;
  }

  
  debug(event);

  const int N = int(2e5);
  Fenw bit(N);
  vector<int> ans(q);
  function<void(int, int)> Cdq = [&](int l, int r) {
    if (l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    Cdq(l, mid);
    Cdq(mid + 1, r);
    vector<array<int, 3>> now;
    for (int i = l; i <= mid; ++i) {
      if (event[i][2] == -1) {
        now.push_back({event[i][0], event[i][1], -1});
      }
    }
    for (int i = mid + 1; i <= r; ++i) {
      if (event[i][2] != -1) {
        now.push_back({event[i][0], event[i][1], event[i][2]});  
      }  
    }
    sort(now.rbegin(), now.rend(), [&](array<int, 3> x, array<int, 3> y) {
      return array<int, 3>{x[0], x[1], -x[2]} < array<int, 3>{y[0], y[1], -y[2]}; 
    });
    vector<int> done;
    int tot = 0;
    for (auto e : now) {
      int x = e[1], id = e[2];
      if (id == -1) {
        done.push_back(x);
        bit.modify(x, +1);
        ++tot;
      } else {
        ans[id] += tot - bit.get(x - 1);
      }
    }
    for (auto e : done) {
      bit.modify(e, -1);
    }
  };
  Cdq(0, n + q - 1);
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << '\n';
  }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 14 ms 1452 KB Output is correct
8 Correct 13 ms 1460 KB Output is correct
9 Correct 12 ms 1416 KB Output is correct
10 Correct 12 ms 1452 KB Output is correct
11 Correct 11 ms 1500 KB Output is correct
12 Correct 9 ms 1460 KB Output is correct
13 Correct 12 ms 1584 KB Output is correct
14 Correct 12 ms 1608 KB Output is correct
15 Correct 13 ms 1616 KB Output is correct
16 Correct 9 ms 1536 KB Output is correct
17 Correct 11 ms 1612 KB Output is correct
18 Correct 8 ms 1484 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 11584 KB Output is correct
2 Correct 457 ms 11572 KB Output is correct
3 Correct 467 ms 11696 KB Output is correct
4 Correct 457 ms 11556 KB Output is correct
5 Correct 368 ms 11716 KB Output is correct
6 Correct 348 ms 11716 KB Output is correct
7 Correct 464 ms 15880 KB Output is correct
8 Correct 447 ms 14104 KB Output is correct
9 Correct 455 ms 15804 KB Output is correct
10 Correct 363 ms 13552 KB Output is correct
11 Correct 419 ms 13348 KB Output is correct
12 Correct 341 ms 12324 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 11584 KB Output is correct
2 Correct 457 ms 11572 KB Output is correct
3 Correct 467 ms 11696 KB Output is correct
4 Correct 457 ms 11556 KB Output is correct
5 Correct 368 ms 11716 KB Output is correct
6 Correct 348 ms 11716 KB Output is correct
7 Correct 464 ms 15880 KB Output is correct
8 Correct 447 ms 14104 KB Output is correct
9 Correct 455 ms 15804 KB Output is correct
10 Correct 363 ms 13552 KB Output is correct
11 Correct 419 ms 13348 KB Output is correct
12 Correct 341 ms 12324 KB Output is correct
13 Correct 500 ms 14496 KB Output is correct
14 Correct 491 ms 14500 KB Output is correct
15 Correct 466 ms 14052 KB Output is correct
16 Correct 483 ms 13728 KB Output is correct
17 Correct 404 ms 13864 KB Output is correct
18 Correct 343 ms 12708 KB Output is correct
19 Correct 496 ms 14500 KB Output is correct
20 Correct 509 ms 14480 KB Output is correct
21 Correct 500 ms 16432 KB Output is correct
22 Correct 352 ms 13480 KB Output is correct
23 Correct 451 ms 13532 KB Output is correct
24 Correct 335 ms 12284 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 14 ms 1452 KB Output is correct
8 Correct 13 ms 1460 KB Output is correct
9 Correct 12 ms 1416 KB Output is correct
10 Correct 12 ms 1452 KB Output is correct
11 Correct 11 ms 1500 KB Output is correct
12 Correct 9 ms 1460 KB Output is correct
13 Correct 12 ms 1584 KB Output is correct
14 Correct 12 ms 1608 KB Output is correct
15 Correct 13 ms 1616 KB Output is correct
16 Correct 9 ms 1536 KB Output is correct
17 Correct 11 ms 1612 KB Output is correct
18 Correct 8 ms 1484 KB Output is correct
19 Correct 460 ms 11584 KB Output is correct
20 Correct 457 ms 11572 KB Output is correct
21 Correct 467 ms 11696 KB Output is correct
22 Correct 457 ms 11556 KB Output is correct
23 Correct 368 ms 11716 KB Output is correct
24 Correct 348 ms 11716 KB Output is correct
25 Correct 464 ms 15880 KB Output is correct
26 Correct 447 ms 14104 KB Output is correct
27 Correct 455 ms 15804 KB Output is correct
28 Correct 363 ms 13552 KB Output is correct
29 Correct 419 ms 13348 KB Output is correct
30 Correct 341 ms 12324 KB Output is correct
31 Correct 500 ms 14496 KB Output is correct
32 Correct 491 ms 14500 KB Output is correct
33 Correct 466 ms 14052 KB Output is correct
34 Correct 483 ms 13728 KB Output is correct
35 Correct 404 ms 13864 KB Output is correct
36 Correct 343 ms 12708 KB Output is correct
37 Correct 496 ms 14500 KB Output is correct
38 Correct 509 ms 14480 KB Output is correct
39 Correct 500 ms 16432 KB Output is correct
40 Correct 352 ms 13480 KB Output is correct
41 Correct 451 ms 13532 KB Output is correct
42 Correct 335 ms 12284 KB Output is correct
43 Correct 528 ms 16484 KB Output is correct
44 Correct 526 ms 16476 KB Output is correct
45 Correct 514 ms 16392 KB Output is correct
46 Correct 494 ms 14868 KB Output is correct
47 Correct 443 ms 15028 KB Output is correct
48 Correct 343 ms 12836 KB Output is correct
49 Correct 552 ms 18332 KB Output is correct
50 Correct 511 ms 16412 KB Output is correct
51 Correct 519 ms 18204 KB Output is correct
52 Correct 431 ms 14960 KB Output is correct
53 Correct 425 ms 14112 KB Output is correct