fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(2e6)+7;
  14.  
  15. int n , p , q , m , a[maxN];
  16. int first[maxN] , last[maxN];
  17. ii dp[maxN];
  18.  
  19. void solve(){
  20.     cin >> n >> p >> q >> m;
  21.     for (int i = 1 ; i <= n ; i++){
  22.         first[i] = +maxN;
  23.         last[i] = -maxN;
  24.     }
  25.     for (int i = 1 ; i <= m ; i++){
  26.         int x , y;
  27.         cin >> x >> y;
  28.         first[y] = min(first[y] , x);
  29.         last[y] = max(last[y] , x);
  30.     }
  31.     dp[0] = {0 , 0};
  32.     for (int i = 1 ; i <= n ; i++){
  33.         dp[i].fi = max(dp[i - 1].fi + p , last[i]);
  34.         dp[i].se = min(dp[i - 1].se + q , first[i] + q - 1);
  35.     }
  36.     int k = -1;
  37.     for (int i = 1 ; i <= n ; i++){
  38.         if (dp[i].fi <= n && n <= dp[i].se) k = i;
  39.     }
  40.     cout << k << "\n";
  41.     int cur = n;
  42.     while (k > 0){
  43.         for (int i = cur - 1 ; i >= 0 ; i--){
  44.             if (dp[k - 1].fi <= i && i <= dp[k - 1].se && p <= cur - i && cur - i <= q && first[k] > i){
  45.                 for (int j = i + 1 ; j <= cur ; j++) a[j] = k;
  46.                 cur = i;
  47.                 k--;
  48.                 break;
  49.             }
  50.         }
  51.     }
  52.     for (int i = 1 ; i <= n ; i++) cout << a[i] << " ";
  53. }
  54.  
  55. #define name "K"
  56.  
  57. int main(){
  58.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  59.     if (fopen(name".INP" , "r")){
  60.         freopen(name".INP" , "r" , stdin);
  61.         freopen(name".OUT" , "w" , stdout);
  62.     }
  63.     int t = 1; //cin >> t;
  64.     while (t--) solve();
  65.     return 0;
  66. }
  67.  
  68.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/vArRiv
language:
C++ (gcc 8.3)
created:
7 days 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!