fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. // Struktura DSU do łączenia przedziałów czasowych
  11. struct DSU {
  12.     vector<int> parent;
  13.     vector<ll> length;
  14.     ll T;
  15.     ll total_starts;
  16.  
  17.     DSU(int n, ll t) : T(t), total_starts(0) {
  18.         parent.resize(n);
  19.         length.assign(n, 0);
  20.         for(int i=0; i<n; ++i) parent[i] = i;
  21.     }
  22.  
  23.     int find(int i) {
  24.         if (parent[i] == i) return i;
  25.         return parent[i] = find(parent[i]);
  26.     }
  27.  
  28.     // Funkcja obliczająca ile startów mieści się w bloku o długości L
  29.     ll f(ll L) {
  30.         return max(0LL, L - T + 1);
  31.     }
  32.  
  33.     void activate(int i, ll len) {
  34.         length[i] = len;
  35.         total_starts += f(len);
  36.     }
  37.  
  38.     void unite(int i, int j) {
  39.         int root_i = find(i);
  40.         int root_j = find(j);
  41.         if (root_i != root_j) {
  42.             total_starts -= f(length[root_i]);
  43.             total_starts -= f(length[root_j]);
  44.             parent[root_i] = root_j;
  45.             length[root_j] += length[root_i];
  46.             total_starts += f(length[root_j]);
  47.         }
  48.     }
  49. };
  50.  
  51. int main() {
  52.     ios::sync_with_stdio(false);
  53.     cin.tie(nullptr);
  54.  
  55.     int n;
  56.     ll t, d;
  57.     if (!(cin >> n >> t >> d)) return 0;
  58.  
  59.     map<ll, int> diff;
  60.     for (int i = 0; i < n; ++i) {
  61.         ll a, b;
  62.         cin >> a >> b;
  63.         diff[a]++;
  64.         diff[b + 1]--;
  65.     }
  66.  
  67.     // Dodanie granic obszaru ucieczki [1, D]
  68.     if (diff.find(1) == diff.end()) diff[1] = 0;
  69.     if (diff.find(d + 1) == diff.end()) diff[d + 1] = 0;
  70.  
  71.     vector<pair<ll, int>> points(diff.begin(), diff.end());
  72.     vector<pair<int, ll>> intervals;
  73.     int current_v = 0;
  74.  
  75.     for (int i = 0; i < (int)points.size() - 1; ++i) {
  76.         current_v += points[i].second;
  77.         ll start = points[i].first;
  78.         ll end = points[i + 1].first;
  79.  
  80.         if (start > d) break;
  81.         ll actual_end = min(d + 1, end);
  82.         if (actual_end > start) {
  83.             intervals.push_back({current_v, actual_end - start});
  84.         }
  85.     }
  86.  
  87.     int m = intervals.size();
  88.     vector<vector<int>> val_to_idx(n + 1);
  89.     for (int i = 0; i < m; ++i) {
  90.         if (intervals[i].first <= n) 
  91.             val_to_idx[intervals[i].first].push_back(i);
  92.     }
  93.  
  94.     DSU dsu(m, t);
  95.     vector<bool> active(m, false);
  96.     vector<ll> results(n + 1, 0);
  97.  
  98.     // Idziemy od największego k, aby budować k-bezpieczeństwo
  99.     for (int k = n; k >= 1; --k) {
  100.         for (int idx : val_to_idx[k]) {
  101.             active[idx] = true;
  102.             dsu.activate(idx, intervals[idx].second);
  103.             if (idx > 0 && active[idx - 1]) dsu.unite(idx, idx - 1);
  104.             if (idx < m - 1 && active[idx + 1]) dsu.unite(idx, idx + 1);
  105.         }
  106.         results[k] = dsu.total_starts;
  107.     }
  108.  
  109.     if (d >= t) results[0] = d - t + 1;
  110.  
  111.     for (int k = 0; k <= n; ++k) {
  112.         if (results[k] > 0) {
  113.             cout << k << " " << results[k] << "\n";
  114.         }
  115.     }
  116.  
  117.     return 0;
  118. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 2 3
1 1
2 2
3 3
2 3
stdout
copy 
0 2
1 2
2 1
https://ideone.com/wG8ubz
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!