fork(1) download 
  1. // D
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define rep(i,a,n) for (int i=a;i<n;i++)
  5. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  6. #define pb push_back
  7. #define mp make_pair
  8. #define all(x) (x).begin(),(x).end()
  9. #define fi first
  10. #define se second
  11. #define SZ(x) ((int)(x).size())
  12. typedef vector<int> VI;
  13. typedef long long ll;
  14. typedef pair<int,int> PII;
  15. const ll mod=1000000007;
  16. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  17. ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
  18. // head
  19.  
  20. const int N=101000;
  21. int _,n,m,pre[N],l,r,ret[N];
  22. int main() {
  23. 	for (scanf("%d",&_);_;_--) {
  24. 		scanf("%d%d",&n,&m);
  25. 		rep(i,1,n+1) pre[i]=i;
  26. 		rep(i,0,m) {
  27. 			scanf("%d%d",&l,&r);
  28. 			pre[r]=min(pre[r],l);
  29. 		}
  30. 		per(i,1,n) pre[i]=min(pre[i],pre[i+1]);
  31. 		int pl=1;
  32. 		set<int> val;
  33. 		rep(i,1,n+1) val.insert(i);
  34. 		rep(i,1,n+1) {
  35. 			while (pl<pre[i]) {
  36. 				val.insert(ret[pl]);
  37. 				pl++;
  38. 			}
  39. 			ret[i]=*val.begin();
  40. 			val.erase(ret[i]);
  41. 		}
  42. 		rep(i,1,n+1) printf("%d%c",ret[i]," \n"[i==n]);
  43. 	}
  44. }
  45.  
Success #stdin #stdout 0s 4204KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/vu31X9
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!