oj.uz

Submission #801372

# Submission time Handle Problem Language Result Execution time Memory
801372 2023-08-02T05:46:43 Z arush_agu Examination (JOI19_examination) C++17
41 / 100
 105 ms 12068 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));

  sort(all(evs));

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

  // for (int i = evs.size() - 1; i >= 0; i--) {
  //   cerr << "I: " << i << "\n";
  //   cerr << "\tType: " << evs[i].t << " Idx: " << evs[i].idx << "\n";
  //   cerr << "\tX: " << evs[i].x << " Y: " << evs[i].y << " Z: " << evs[i].z
  //        << "\n";
  // }

  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:177:11: warning: unused variable 'start' [-Wunused-variable]
  177 |   clock_t start = clock();
      |           ^~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1856 KB Output is correct
4 Runtime error 2 ms 3652 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 90 ms 11512 KB Output is correct
2 Correct 89 ms 11580 KB Output is correct
3 Correct 80 ms 11564 KB Output is correct
4 Correct 66 ms 10784 KB Output is correct
5 Correct 75 ms 10824 KB Output is correct
6 Correct 49 ms 10072 KB Output is correct
7 Correct 74 ms 11436 KB Output is correct
8 Correct 74 ms 11424 KB Output is correct
9 Correct 72 ms 11464 KB Output is correct
10 Correct 64 ms 10672 KB Output is correct
11 Correct 80 ms 10660 KB Output is correct
12 Correct 46 ms 9644 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 11512 KB Output is correct
2 Correct 89 ms 11580 KB Output is correct
3 Correct 80 ms 11564 KB Output is correct
4 Correct 66 ms 10784 KB Output is correct
5 Correct 75 ms 10824 KB Output is correct
6 Correct 49 ms 10072 KB Output is correct
7 Correct 74 ms 11436 KB Output is correct
8 Correct 74 ms 11424 KB Output is correct
9 Correct 72 ms 11464 KB Output is correct
10 Correct 64 ms 10672 KB Output is correct
11 Correct 80 ms 10660 KB Output is correct
12 Correct 46 ms 9644 KB Output is correct
13 Correct 81 ms 11976 KB Output is correct
14 Correct 105 ms 12068 KB Output is correct
15 Correct 77 ms 11568 KB Output is correct
16 Correct 68 ms 11200 KB Output is correct
17 Correct 67 ms 11204 KB Output is correct
18 Correct 48 ms 10092 KB Output is correct
19 Correct 78 ms 11944 KB Output is correct
20 Correct 89 ms 11912 KB Output is correct
21 Correct 81 ms 11944 KB Output is correct
22 Correct 74 ms 10660 KB Output is correct
23 Correct 63 ms 10680 KB Output is correct
24 Correct 44 ms 9660 KB Output is correct

Subtask #4
0 / 57.0

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