oj.uz

Submission #801393

# Submission time Handle Problem Language Result Execution time Memory
801393 2023-08-02T05:52:06 Z arush_agu Examination (JOI19_examination) C++17
41 / 100
 216 ms 29288 KB 
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e9;
const ld EPS = 1e-9;

struct SegTree {
  int n;
  vi t;

  void init(int n_) {
    n = n_;
    t = vi(2 * n + 10);
  }

  int query(int l, int r) {
    int res = 0;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1)
        res += t[l++];
      if (r & 1)
        res += t[--r];
    }
    return res;
  }

  void upd(int p, int d) {
    for (t[p += n] += d; p > 1; p /= 2)
      t[p / 2] = t[p] + t[p ^ 1];
  }
} st1, st2;

struct Ev {
  int x, y, z, idx, t;
  Ev(int x, int y, int z, int idx, int t) : x(x), y(y), z(z), idx(idx), t(t) {}
  bool operator<(const Ev &other) const {
    return ii{z, -t} < ii{other.z, -other.t};
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  vi s(n), t(n);
  for (int i = 0; i < n; i++)
    cin >> s[i] >> t[i];
  vector<pair<ii, ii>> qs(q);
  for (int i = 0; i < q; i++)
    cin >> qs[i].first.first >> qs[i].first.second >> qs[i].second.first,
        qs[i].second.second = i;

  vector<Ev> evs;
  for (int i = 0; i < n; i++)
    evs.push_back(Ev(s[i], t[i], s[i] + t[i], -1, -1));
  for (auto &[a, b] : qs)
    evs.push_back(
        Ev(a.first, a.second, max(b.first, a.first + a.second), b.second, 1));

  vi comp;
  for (auto &e : evs)
    comp.push_back(e.x), comp.push_back(e.y), comp.push_back(e.z);
  sort(all(comp));
  comp.erase(unique(all(comp)));

  auto get = [&](int x) { return lower_bound(all(comp), x) - comp.begin(); };
  for (auto &e : evs)
    e.x = get(e.x), e.y = get(e.y), e.z = get(e.z);

  sort(all(evs));

  const int MAXS = 1e6 + 10;
  st1.init(MAXS), st2.init(MAXS);

  vi ans(q, -1);

  int in = 0;
  for (int qid = evs.size() - 1; qid >= 0; qid--) {
    Ev &e = evs[qid];
    if (e.t == 1) {
      ans[e.idx] = max(0, st1.query(e.x, MAXS) + st2.query(e.y, MAXS) - in);
    } else {
      in++;
      st1.upd(e.x, 1), st2.upd(e.y, 1);
    }
  }

  for (int i = 0; i < q; i++)
    cout << ans[i] << "\n";
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  clock_t start = clock();

  int test_cases = 1;
  // cin >> test_cases;

  while (test_cases--)
    solve();

#ifdef DEBUG
  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
#endif
  return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:180:11: warning: unused variable 'start' [-Wunused-variable]
  180 |   clock_t start = clock();
      |           ^~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15956 KB Output is correct
2 Correct 6 ms 15956 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Runtime error 1 ms 596 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 29216 KB Output is correct
2 Correct 203 ms 29172 KB Output is correct
3 Correct 201 ms 29152 KB Output is correct
4 Correct 172 ms 29244 KB Output is correct
5 Correct 159 ms 29176 KB Output is correct
6 Correct 106 ms 29192 KB Output is correct
7 Correct 198 ms 29168 KB Output is correct
8 Correct 208 ms 29252 KB Output is correct
9 Correct 193 ms 29288 KB Output is correct
10 Correct 149 ms 28980 KB Output is correct
11 Correct 150 ms 29044 KB Output is correct
12 Correct 80 ms 28916 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 29216 KB Output is correct
2 Correct 203 ms 29172 KB Output is correct
3 Correct 201 ms 29152 KB Output is correct
4 Correct 172 ms 29244 KB Output is correct
5 Correct 159 ms 29176 KB Output is correct
6 Correct 106 ms 29192 KB Output is correct
7 Correct 198 ms 29168 KB Output is correct
8 Correct 208 ms 29252 KB Output is correct
9 Correct 193 ms 29288 KB Output is correct
10 Correct 149 ms 28980 KB Output is correct
11 Correct 150 ms 29044 KB Output is correct
12 Correct 80 ms 28916 KB Output is correct
13 Correct 207 ms 29224 KB Output is correct
14 Correct 204 ms 29164 KB Output is correct
15 Correct 201 ms 29208 KB Output is correct
16 Correct 164 ms 29172 KB Output is correct
17 Correct 166 ms 29164 KB Output is correct
18 Correct 94 ms 29168 KB Output is correct
19 Correct 216 ms 29212 KB Output is correct
20 Correct 209 ms 29236 KB Output is correct
21 Correct 201 ms 29212 KB Output is correct
22 Correct 151 ms 29040 KB Output is correct
23 Correct 152 ms 29036 KB Output is correct
24 Correct 78 ms 28848 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15956 KB Output is correct
2 Correct 6 ms 15956 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Runtime error 1 ms 596 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -