SHARE
TWEET

1148E

hung_mine Oct 9th, 2019 (edited) 100 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /// from HUNG MINE with love <3
  5. typedef pair <long long, long long> ii;
  6. typedef pair <ii, long long> iii;
  7. struct st {
  8.       long long s, pos;
  9. };
  10. st a[300001];
  11. long long n, t[300001], sum = 0;
  12. stack <ii> p;
  13. vector <iii> ans;
  14. bool cmp (st a, st b) {
  15.       return a.s < b.s;
  16. }
  17. int main () {
  18.       //freopen (".inp", "r", stdin);
  19.       //freopen (".out", "w", stdout);
  20.       ios_base :: sync_with_stdio (0);
  21.       cin.tie (0);
  22.       cout.tie (0);
  23.       cin >> n;
  24.       for (int i = 1; i <= n; ++ i) {
  25.             cin >> a[i].s;
  26.             a[i].pos = i;
  27.       }
  28.       sort (a + 1, a + n + 1, cmp);
  29.       for (int i = 1; i <= n; ++ i) {
  30.             cin >> t[i];
  31.       }
  32.       sort (t + 1, t + n + 1);
  33.       for (int i = 1; i <= n; ++ i) {
  34.             sum += t[i] - a[i].s;
  35.       }
  36.       if (sum != 0) {
  37.             cout << "NO";
  38.       }
  39.       else {
  40.             for (int i = 1; i <= n; ++ i) {
  41.                   //if (p.size ()) cout << p.top ().first << " " << p.top ().second << "\n";
  42.                   if (t[i] - a[i].s > 0) {
  43.                         p.push (ii (i, t[i] - a[i].s));
  44.                   }
  45.                   else if (t[i] - a[i].s < 0) {
  46.                         while (p.size ()) {
  47.                               if ((a[i].s - a[p.top ().first].s) >= 2 * p.top ().second) {//cerr << 1;
  48.                                     ans.push_back (iii (ii (a[p.top ().first].pos, a[i].pos),p.top ().second));
  49.                                     a[i].s -= p.top ().second;
  50.                                     a[p.top ().first].s += p.top ().second;
  51.                                     p.top ().second -= p.top ().second;
  52.  
  53.  
  54.                               }
  55.                               else {//cerr << 2;
  56.                                     ans.push_back (iii (ii (a[p.top ().first].pos, a[i].pos),a[i].s - t[i]));
  57.                                     a[p.top ().first].s += (a[i].s - t[i]);
  58.                                     p.top ().second -= (a[i].s - t[i]);
  59.                                     a[i].s -= (a[i].s - t[i]);
  60.                               }
  61.                               if (t[i] - a[i].s >= 0) break;
  62.                               if (p.top ().second == 0) p.pop ();
  63.                         }
  64.                         if (t[i] - a[i].s > 0) {
  65.                               p.push (ii (i, t[i] - a[i].s));
  66.                         }
  67.                   }
  68.             }
  69.             for (int i = 1; i <= n; ++ i) {
  70.                   if (a[i].s != t[i]) return cout << "NO", 0;
  71.             }
  72.             cout << "YES\n";
  73.             cout << ans.size () << "\n";
  74.             for (auto val : ans) {
  75.                   cout << val.first.first << " " << val.first.second << " " << val.second << "\n";
  76.             }
  77.       }
  78. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top