Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define fori(i,n) for(int i =0;i<n;i++)
- #define pb push_back
- #define ll long long
- #define int long long
- #define F first
- #define S second
- #define mp make_pair
- #define rev(a) reverse(a.begin(),a.end())
- #define srt(a) sort(a.begin(),a.end())
- #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout.precision(15);
- int mod = 1000000007;
- int pow(int a, int b) {
- int ans = 1;
- a %= mod;
- while(b) {
- if(b%2) {
- ans *= a;
- ans %= mod;
- }
- b /= 2;
- a *= a;
- a %= mod;
- }
- return ans;
- }
- std::vector<int> g[500005];
- bool vis[500005];
- int con=0,edges=0;
- void dfs(int a) {
- stack<int> stc;
- stc.push(a);
- while(!stc.empty()) {
- int t = stc.top();
- stc.pop();
- vis[t] = 1;
- for(int i = 0;i<g[t].size();i++) {
- if (!vis[g[t][i]]) {
- vis[g[t][i]] = 1;
- stc.push(g[t][i]);
- }
- }
- }
- }
- int32_t main() {
- int n;
- std::vector<pair<pair<int,int>,int>> ranges;
- cin>>n;
- fori(i,n) {
- int x,y;
- cin>>x>>y;
- ranges.pb(mp(mp(x,y),i));
- }
- set<pair<int,int>> s;
- srt(ranges);
- fori(i,n) {
- auto it = s.lower_bound(mp(ranges[i].F.F,0));
- while (it != s.end() && it->F < ranges[i].F.S) {
- g[ranges[i].S].pb(it->S);
- g[it->S].pb(ranges[i].S);
- // cout<<endl<<it->S<<" "<<ranges[i].S<<" an edge";
- it++;
- }
- s.insert(mp(ranges[i].F.S,ranges[i].S));
- }
- ranges.clear();
- s.clear();
- fori(i,n) {
- edges += g[i].size();
- if(!vis[i]) {
- dfs(i);
- con++;
- }
- }
- if (edges/2 == n-1 && con == 1) {
- cout<<"YES";
- } else {
- cout<<"NO";
- }
- // cout<<"\n"<<edges<<" "<<con;
- }
Add Comment
Please, Sign In to add comment