Advertisement
Guest User

Untitled

a guest
Dec 19th, 2014
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <deque>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18.  
  19. #define fst first
  20. #define snd second
  21. #define all(x) (x).begin(), (x).end()
  22. #define clr(a, v) memset( a , v , sizeof(a) )
  23. #define pb push_back
  24. #define mp make_pair
  25. #define sz size()
  26. #define FORN( i , s , n ) for( int i = (s) ; i < (n) ; i++ )
  27. #define FOR( i , n ) FORN( i , 0 , n )
  28. #define FORIT( i , x ) for( typeof x.begin() i = x.begin() ; i != x.end() ; i++ )
  29. #define trace(x)    cerr << #x << ": " << x << endl;
  30. #define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  31. #define read ios::sync_with_stdio(false)
  32.  
  33. using namespace std;
  34.  
  35. typedef long long int64;
  36. typedef vector <int> vi;
  37. typedef pair <int,int> ii;
  38. typedef vector <string> vs;
  39. typedef vector <ii> vii;
  40.  
  41. struct seg{
  42.     int ini, type, fin, cnt, ind;
  43.     bool operator <  (seg V) const{
  44.         if ( ini !=V.ini  ) return ini <V.ini ;
  45.         if ( type!=V.type ) return type<V.type;
  46.         return fin<V.fin;
  47.     }
  48. } V[2*100002] ;
  49.  
  50. struct act{
  51.     int fin;
  52.     int ind;
  53.     int cnt;
  54.     bool operator <  (act V) const{
  55.         if ( fin !=V.fin  ) return fin <V.fin ;
  56.         return ind<V.ind;
  57.     }
  58. };
  59.  
  60. int main(){
  61.     int N,M;
  62.     scanf("%d",&N);
  63.     seg aux;
  64.     FOR(i,N){
  65.         scanf("%d %d",&aux.ini,&aux.fin);
  66.         aux.ind=i+1;
  67.         aux.type=2;
  68.         V[i]=aux;
  69.     }
  70.     scanf("%d",&M);
  71.     FOR(i,M){
  72.         scanf("%d %d %d", &aux.ini, &aux.fin, &aux.cnt);
  73.         aux.ind=i+1;
  74.         aux.type=1;
  75.         V[N+i]=aux;
  76.     }
  77.     sort(V,V+(N+M));
  78.  
  79.     set < act > S;
  80.     set < act >::iterator it;
  81.     act p;
  82.     int ans[N];
  83.     int use[M];
  84.     FOR(i,M) use[i]=0;
  85.     bool flag=1;
  86.     FOR(i,N+M){
  87.         if ( V[i].type==1 ){
  88.             p.fin=V[i].fin;
  89.             p.ind=V[i].ind;
  90.             p.cnt=V[i].cnt;
  91.             S.insert(p);
  92.         }
  93.         else{
  94.             p.fin=V[i].fin;
  95.             p.ind=-1;
  96.             it=lower_bound(all(S),p);
  97.             if ( it==S.end() ) {flag=0; break;}
  98.             p=*it;
  99.             ans[V[i].ind-1]=p.ind;
  100.             use[p.ind-1]++;
  101.             if ( use[p.ind-1]==p.cnt ) S.erase(it);
  102.         }
  103.     }
  104.  
  105.     if (flag) {
  106.         printf("YES\n")
  107.         FOR(i,N) printf("%d ",ans[i]);
  108.     }
  109.     else printf("NO\n");
  110.     return 0;
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement