G2A Many GEOs
SHARE
TWEET

Untitled

aayyk Apr 8th, 2020 151 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <climits>
  9. #include <string>
  10. #include <set>
  11. #include <cmath>
  12. #include <map>
  13. #include <unordered_map>
  14. #include <numeric>
  15. #include <random>
  16. #include <memory>
  17. #include <chrono>
  18. #include <functional>
  19. #include <unordered_set>
  20. #include <cstring>
  21. #include <cassert>
  22. #include <bitset>
  23. #ifdef LOCAL
  24. #include "debug.h"
  25. #else
  26. #define debug(x...)
  27. #endif
  28. //#define int ll
  29. //#pragma GCC optimize("Ofast")
  30.  
  31.  
  32. using namespace std;
  33. typedef long long ll;
  34. typedef long double ld;
  35. typedef pair <int, int> pii;
  36. #define sz(x) int((x).size())
  37.  
  38. #ifndef LOCAL
  39.     mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  40. #else
  41.     mt19937 rng(228);
  42. #endif
  43.  
  44. const int N = 3e5 + 7;
  45. const int inf = INT_MAX / 2;
  46. const ll INF = LLONG_MAX / 3;
  47. const int MOD = 998244353;
  48. const ld eps = 1e-6;
  49. const string cars[] = {"🚗", "🚕", "🚙"};
  50.  
  51. int l[N], r[N], a[N];
  52.  
  53. struct Tree {
  54.     int t[4 * N];
  55.  
  56.     Tree () {
  57.         memset(t, -1, sizeof t);
  58.     }
  59.  
  60.     void push(int v) {
  61.         if (t[v] != -1) {
  62.             t[2 * v] = t[2 * v + 1] = t[v];
  63.             t[v] = -1;
  64.         }
  65.     }
  66.  
  67.     void update(int v, int tl, int tr, int l, int r, int val) {
  68.         if (l > r) {
  69.             return;
  70.         }
  71.  
  72.         if (tl == l && tr == r) {
  73.             t[v] = val;
  74.         }
  75.         else {
  76.             push(v);
  77.  
  78.             int tm = (tl + tr) / 2;
  79.  
  80.             update(2 * v, tl, tm, l, min(r, tm), val);
  81.             update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
  82.         }
  83.     }
  84.  
  85.     int get(int v, int tl, int tr, int pos) {
  86.         if (tl == tr) {
  87.             return t[v];
  88.         }
  89.         else {
  90.             push(v);
  91.  
  92.             int tm = (tl + tr) / 2;
  93.             if (pos <= tm) {
  94.                 return get(2 * v, tl, tm, pos);
  95.             }
  96.             else {
  97.                 return get(2 * v + 1, tm + 1, tr, pos);
  98.             }
  99.         }
  100.     }
  101. };
  102.  
  103. signed main() {
  104. #ifdef LOCAL
  105.     freopen("input.txt", "r", stdin);
  106.     //freopen("output.txt", "w", stdout);
  107. #endif
  108.     cout << fixed << setprecision(9);
  109.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  110.  
  111.     Tree tree = Tree();
  112.  
  113.     int n, m;
  114.     cin >> n >> m;
  115.  
  116.     fill(l, l + N, inf);
  117.     for (int i = 0; i < n; i++) {
  118.         cin >> a[i];
  119.         l[a[i]] = min(i, l[a[i]]);
  120.         r[a[i]] = max(i, r[a[i]]);
  121.     }
  122.  
  123.     vector < tuple < int, int, int > > v;
  124.     for (int i = 1; i <= m; i++) {
  125.         if (l[i] != inf) {
  126.             v.emplace_back(l[i], r[i], i);
  127.         }
  128.     }
  129.  
  130.     sort(v.begin(), v.end());
  131.  
  132.     set < int > s;
  133.     for (auto x : v) {
  134.         int l, r, c;
  135.         tie(l, r, c) = x;
  136.         debug(l, r, c);
  137.  
  138.         if (!s.empty() && l <= *s.rbegin() && r > *s.rbegin()) {
  139.             return cout << "-1\n", 0;
  140.         }
  141.  
  142.         s.insert(r);
  143.     }
  144.  
  145.     sort(v.begin(), v.end(), [](tuple < int, int, int > x, tuple < int, int, int > y) {
  146.         return get < 0 > (x) < get < 0 > (y);
  147.     });
  148.  
  149.    
  150.     for (auto x : v) {
  151.         int l, r, c;
  152.         tie(l, r, c) = x;
  153.  
  154.         //cout << c << " " << l + 1 << " " << r + 1 << "\n";
  155.         tree.update(1, 0, n - 1, l, r, c);
  156.     }
  157.  
  158.     int flag = 1;
  159.     for (int i = 0; i < n; i++) {
  160.         if (tree.get(1, 0, n - 1, i) != a[i]) {
  161.             flag = 0;
  162.             break;
  163.         }
  164.     }
  165.  
  166.     if (flag) {
  167.         cout << sz(v) << "\n";
  168.         for (auto x : v) {
  169.             int l, r, c;
  170.             tie(l, r, c) = x;
  171.  
  172.             cout << c << " " << l + 1 << " " << r + 1 << "\n";
  173.             //tree.update(1, 0, n - 1, l, r, c);
  174.         }
  175.     }
  176.     else {
  177.         cout << "-1\n";
  178.     }
  179.  
  180.     return 0;
  181. }
RAW Paste Data
Ledger Nano X - The secure hardware wallet
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