Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- int main() {
- ios_base::sync_with_stdio(false);
- int n;
- ll R, D;
- cin >> n >> R >> D;
- vector<pair<ll, ll>> discos(n);
- for(int i = 0; i < n; i++) {
- cin >> discos[i].first >> discos[i].second;
- }
- sort(discos.begin(), discos.end());
- ll total_R = 2 * R;
- vector<pair<ll, ll>> q;
- q.reserve(n);
- ll active = 0, total = 0;
- int F =0 ;
- for(int i = 0; i < n; i++) {
- ll pos = discos[i].first, y = discos[i].second;
- ll need = (y + D - 1) / D;
- while(F < (int) q.size() and q[F].first < pos) {
- active -= q[F].second;
- F++;
- }
- if(need > active) {
- ll add = need - active;
- total += add;
- q.push_back(make_pair(pos + total_R, add));
- active += add;
- }
- }
- cout << total << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment