fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int Mod=998244353;
  5. const ll INF = -10000000000000;
  6.  
  7. void solve() {
  8.     int n;
  9.     cin >> n;
  10.     vector<int> d(n),L(n), R(n);
  11.  
  12.     for(int i = 0; i < n; i++) cin >> d[i];
  13.     for(int i = 0; i < n; i++) cin >> L[i] >> R[i];
  14.  
  15.     vector<int> a(n+1), b(n+1);
  16.     a[0] = b[0] = 0;
  17.  
  18.     bool ok = true;
  19.     for(int i = 1; i <= n; i++){
  20.         int low, high;
  21.         if(d[i-1] == -1){
  22.             low = a[i-1];
  23.             high = b[i-1] + 1;
  24.         } else {
  25.             low = a[i-1] + d[i-1];
  26.             high = b[i-1] + d[i-1];
  27.         }
  28.         low = max(low, L[i-1]);
  29.         high = min(high, R[i-1]);
  30.         if(low > high){
  31.             ok = false;
  32.             break;
  33.         }
  34.         a[i] = low;
  35.         b[i] = high;
  36.     }
  37.     if(!ok){
  38.         cout << "-1\n";
  39.         return;
  40.     }
  41.     vector<int> ans(n);
  42.     int h = a[n];
  43.     for(int i = n; i >= 1; i--){
  44.         if(d[i-1] != -1){
  45.             ans[i-1] = d[i-1];
  46.             h -= d[i-1];
  47.         } else {
  48.             if(h >= a[i-1] && h <= b[i-1]){
  49.                 ans[i-1] = 0;
  50.             } else {
  51.                 ans[i-1] = 1;
  52.                 h -= 1;
  53.             }
  54.         }
  55.     }
  56.  
  57.     for(int i = 0; i < n; i++)  cout << ans[i] << " ";
  58.     cout << '\n';
  59.             }
  60.  
  61.  
  62. int main(){ 
  63.     ios::sync_with_stdio(false);
  64.     cin.tie(nullptr);
  65.  
  66.     int t;
  67.     cin >> t;
  68.     while (t--) solve();
  69.  
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
5
4
0 -1 -1 1
0 4
1 2
2 4
1 4
3
0 -1 -1
0 1
2 2
0 3
2
-1 -1
0 0
2 2
8
-1 -1 1 -1 -1 0 0 -1
0 0
0 1
0 2
0 2
1 3
0 4
2 5
4 5
1
0
1 1
stdout 
0 1 1 1 
-1
-1
0 1 1 0 1 0 0 1 
-1
https://ideone.com/1EaCkT
language:
C++ (gcc 8.3)
created:
15 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!