#include "gift.h" #include <bits/stdc++.h> using namespace std; const int nx=5e5+5; int qs[nx], lst, mx[nx]; string s; vector<int> t[nx]; int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) { for (int i=0; i<r; i++) if (x[i]==1) qs[a[i]]++, qs[b[i]]--; char cur='R'; for (int i=0; i<n; i++) { qs[i+1]+=qs[i]; mx[i]=-1; s+=cur; if (!qs[i]) cur=(cur=='R')?'B':'R'; } for (int i=0; i<r; i++) if (x[i]==2) mx[b[i]]=max(mx[b[i]], a[i]); lst=-1; for (int i=0; i<n; i++) { if (i>0&&s[i]!=s[i-1]) lst=i-1; if (lst<mx[i]) return 0; } craft(s); return 1; }