Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <climits>
- #include <string>
- #include <set>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <numeric>
- #include <random>
- #include <memory>
- #include <chrono>
- #include <functional>
- #include <unordered_set>
- #include <cstring>
- #include <cassert>
- #include <bitset>
- #ifdef LOCAL
- #include "debug.h"
- #else
- #define debug(x...)
- #endif
- //#define int ll
- //#pragma GCC optimize("Ofast")
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair <int, int> pii;
- #define sz(x) int((x).size())
- #ifndef LOCAL
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(228);
- #endif
- const int N = 3e5 + 7;
- const int inf = INT_MAX / 2;
- const ll INF = LLONG_MAX / 3;
- const int MOD = 998244353;
- const ld eps = 1e-6;
- const string cars[] = {"🚗", "🚕", "🚙"};
- int l[N], r[N], a[N];
- struct Tree {
- int t[4 * N];
- Tree () {
- memset(t, -1, sizeof t);
- }
- void push(int v) {
- if (t[v] != -1) {
- t[2 * v] = t[2 * v + 1] = t[v];
- t[v] = -1;
- }
- }
- void update(int v, int tl, int tr, int l, int r, int val) {
- if (l > r) {
- return;
- }
- if (tl == l && tr == r) {
- t[v] = val;
- }
- else {
- push(v);
- int tm = (tl + tr) / 2;
- update(2 * v, tl, tm, l, min(r, tm), val);
- update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
- }
- }
- int get(int v, int tl, int tr, int pos) {
- if (tl == tr) {
- return t[v];
- }
- else {
- push(v);
- int tm = (tl + tr) / 2;
- if (pos <= tm) {
- return get(2 * v, tl, tm, pos);
- }
- else {
- return get(2 * v + 1, tm + 1, tr, pos);
- }
- }
- }
- };
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(9);
- ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
- Tree tree = Tree();
- int n, m;
- cin >> n >> m;
- fill(l, l + N, inf);
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- l[a[i]] = min(i, l[a[i]]);
- r[a[i]] = max(i, r[a[i]]);
- }
- vector < tuple < int, int, int > > v;
- for (int i = 1; i <= m; i++) {
- if (l[i] != inf) {
- v.emplace_back(l[i], r[i], i);
- }
- }
- sort(v.begin(), v.end());
- set < int > s;
- for (auto x : v) {
- int l, r, c;
- tie(l, r, c) = x;
- debug(l, r, c);
- if (!s.empty() && l <= *s.rbegin() && r > *s.rbegin()) {
- return cout << "-1\n", 0;
- }
- s.insert(r);
- }
- sort(v.begin(), v.end(), [](tuple < int, int, int > x, tuple < int, int, int > y) {
- return get < 0 > (x) < get < 0 > (y);
- });
- for (auto x : v) {
- int l, r, c;
- tie(l, r, c) = x;
- //cout << c << " " << l + 1 << " " << r + 1 << "\n";
- tree.update(1, 0, n - 1, l, r, c);
- }
- int flag = 1;
- for (int i = 0; i < n; i++) {
- if (tree.get(1, 0, n - 1, i) != a[i]) {
- flag = 0;
- break;
- }
- }
- if (flag) {
- cout << sz(v) << "\n";
- for (auto x : v) {
- int l, r, c;
- tie(l, r, c) = x;
- cout << c << " " << l + 1 << " " << r + 1 << "\n";
- //tree.update(1, 0, n - 1, l, r, c);
- }
- }
- else {
- cout << "-1\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement