제출 #401356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401356		erray	Examination (JOI19_examination)	C++11	100 / 100	552 ms	18332 KiB

examination

// 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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57