#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod ((int)1e9 + 7)
#define max 200001
int gcdExtended(int a, int b, int *x, int *y) {
if (a == 0) {
*x = 0;
*y = 1;
return b;
}
int x1, y1;
int gcd = gcdExtended(b % a, a, &x1, &y1);
*x = y1 - (b / a) * x1;
*y = x1;
return gcd;
}
int modInverse(int b, int m) {
int x, y;
int g = gcdExtended(b, m, &x, &y);
if (g != 1)
return -1;
return (x % m + m) % m;
}
bool cmp(pair<char, int>& a, pair<char, int>& b) {
return a.second > b.second;
}
void sortMap(map<char, int>& M) {
vector<pair<char, int> > A;
for (auto& it : M) A.push_back(it);
sort(A.begin(), A.end(), cmp);
}
void solve() {
int n;
cin >> n;
//vector<pair<pair<int, int>, int>> ranges;
// for (int i = 0; i < n; i++) {
// int l, r;
// cin >> l >> r;
// ranges.push_back({{l, r}, i});
// }
// sort(ranges.begin(), ranges.end(), [](const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) {
// if (a.first.first != b.first.first)
// return a.first.first < b.first.first;
// return a.first.second < b.first.second;
// });
vector<pair<int, int>> range(n);
for (auto &p : range) cin >> p.first >> p.second;
// priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// vector<int> assigned(n, 0);
// string result(n + 1, '0');
// result[n] = '\0';
unordered_map<int, int> mp;
for (const auto &p : range) {
if (p.first == p.second) {
mp[p.first]++;
}
}
// int idx = 0, val = 1;
vector<int> v;
for (const auto &[value, count] : mp) {
v.push_back(value);
cnt[value] += count;
}
sort(v.begin(), v.end());
string res;
res.reserve(n);
// while (idx < n || !pq.empty()) {
// while (idx < n && ranges[idx].first.first <= val) {
// pq.push({ranges[idx].first.second, ranges[idx].second});
// idx++;
// }
// while (!pq.empty() && pq.top().first < val) {
// pq.pop();
// }
// if (!pq.empty()) {
// auto [right, index] = pq.top();
// pq.pop();
// if (val >= ranges[index].first.first && val <= ranges[index].first.second) {
// assigned[index] = val;
// result[index] = '1';
// val++;
// }
// } else {
// val++;
// }
// }
for (const auto &[i, j] : range) {
if(i==j){
res += (mp[i] > 1) ? '0' : '1';
continue;
}
if (i < j) {
// for (int k : v) {
// if (k > j) break;
// if (k >= i) x++;
// }
int l = lower_bound(v.begin(), v.end(), i) - v.begin();
int r = upper_bound(v.begin(), v.end(), j) - v.begin();
int x = r - l;
res += (x < j - i + 1) ? '1' : '0';
} else {
res += (cnt[i] <= 1) ? '1' : '0';
}
}
cout << res << "\n";
for (auto &[v, cnt] : mp) {
cnt[v] -= cnt;
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
vector<int> cnt(max, 0);
while (t--) {
solve();
}
return 0;
}
Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}