Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- #define mod 998244353
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- int t;
- cin>>t;
- while(t--)
- {
- int n,m;
- cin>>n>>m;
- int l[m];
- int r[m];
- for(int i=0;i<m;i++){cin>>l[i]>>r[i];l[i]--;r[i]--;}
- vector<int> opens[n+1];
- vector<int> closes[n+1];
- for(int i=0;i<m;i++)
- {
- opens[l[i]].push_back(i);
- closes[r[i]].push_back(i);
- }
- set<pair<int,int>> s; //(close,i)
- int dp[n+1];
- dp[n]=0;
- for(int i=n-1;i>=0;i--)
- {
- for(auto x:closes[i]){s.insert({r[x],x});}
- dp[i]=dp[i+1];
- if(!s.empty())
- {
- dp[i]=max(dp[i],(int)(s.size())+dp[(*(s.rbegin())).first+1]);
- }
- for(auto x:opens[i]){s.erase({r[x],x});}
- }
- cout<<dp[0]<<"\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement