Submission #280003

#	Time	Username	Problem	Language	Result	Execution time	Memory
280003		erray	Examination (JOI19_examination)	C++17	0 / 100	373 ms	14200 KiB

examination

// author: erray
#undef DEBUG
#include<bits/stdc++.h>
 
using namespace std;

template<typename T, typename F> string to_string(pair<T, F> p);
template<typename T, typename F, typename Tr> string to_string(tuple<T, F, Tr> p);
template<typename T, typename F, typename Tr, typename Th> string to_string(tuple<T, F, Tr, Th> p);
string to_string(string s) {
  return '"' + s + '"';
}
string to_string(char c) {
  return (string) "'" + c + "'";
}
string to_string(const char* p) {
  return to_string((string) p);
}
string to_string(bool B) {
  return (B ? "true" : "false");
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < (int) v.size(); ++i) {
    if ((int) res.size() > 1) res += ", ";
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template<size_t T> string to_string(bitset<T> bs) {
  return bs.to_string();
}
template<typename T> string to_string(T v) {
  string res = "{";
  for (auto& el : v) {
    if ((int) res.size() > 1) res += ", ";
    res += to_string(el);
  }
  res += "}";
  return res;
}
template<typename T, typename F> string to_string(pair<T, F> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
template<typename T, typename F, typename Tr> string to_string(tuple<T, F, Tr> p) {
  return '(' + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ')';
}
template<typename T, typename F, typename Tr, typename Th> string to_string(tuple<T, F, Tr, Th> p) {
    return '(' + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ')';
}
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
#define int long long
int32_t main () {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
  sort(a.begin(), a.end());
  
  vector<tuple<int, int, int>> ord(n);
  for (int i = 0; i < n; ++i) {
    ord[i] = make_tuple(a[i].first, a[i].second, i);  
  }
  sort(ord.rbegin(), ord.rend(), [&](auto x, auto y) {
    return get<1>(x) < get<1>(y);
  });
  vector<int> ind(n), sum(n);
  for (int i = 0; i < n; ++i) {
    ind[get<2>(ord[i])] = i;
    sum[i] = get<0>(ord[i]) + get<1>(ord[i]);
  }
  debug(ord, a);

  const int BLOCK = (int) ceil(sqrt(n)), sz = (n - 1) / BLOCK + 1;
  vector<vector<int>> dec(sz);
  vector<int> topPoint(sz);
  for (int i = 0; i < n; ++i) {
    dec[i / BLOCK].push_back(sum[i]);
    topPoint[i / BLOCK] = get<1>(ord[i]);
  }
  for (int i = 0; i < sz; ++i) {
    sort(dec[i].rbegin(), dec[i].rend());
  }
  debug(BLOCK, sz, topPoint);
  debug(dec);
  vector<tuple<int, int, int, int>> q(m);
  vector<int> ans(m);
  for (int i = 0; i < m; ++i) {
    cin >> get<0>(q[i]) >> get<1>(q[i]) >> get<2>(q[i]);
    get<3>(q[i]) = i;
  }
  sort(q.begin(), q.end());

  debug(sum);
  int lst = 0;
  vector<bool> mark(n);
  for (auto[x, y, z, wh] : q) {
    debug(x, y, z, wh, lst);

    while (lst < n && a[lst].first < x) {
      int mind = ind[lst];
      mark[mind] = true;
      dec[mind / BLOCK].erase(lower_bound(dec[mind / BLOCK].begin(), dec[mind / BLOCK].end(), a[lst].first + a[lst].second, [](int tx, int ty) {
        return tx > ty;
      }));
      ++lst;
    }
    int cur = 0, res = 0;
    while (cur < sz && topPoint[cur] >= y) {
      res += (int) (lower_bound(dec[cur].begin(), dec[cur].end(), z + 1, [](int tx, int ty) {
        return tx > ty;
      }) - dec[cur].begin());  
      ++cur;
    } 
    debug(cur, res);
    cur *= BLOCK;
    while (cur < n && get<1>(ord[cur]) >= y) {
      res += (!mark[cur] && sum[cur] >= z);  
      ++cur;
    }
    debug(cur);
    ans[wh] = res;
  }
  for (auto el : ans) cout << el << ' ';
}

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