SHOW:
|
|
- or go back to the newest paste.
| 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 | - | cin>>N; |
| 52 | + | int ind; |
| 53 | - | vector < seg > V; |
| 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 | - | V.pb(aux); |
| 59 | + | |
| 60 | int main(){
| |
| 61 | - | cin>>M; |
| 61 | + | |
| 62 | scanf("%d",&N);
| |
| 63 | seg aux; | |
| 64 | FOR(i,N){
| |
| 65 | scanf("%d %d",&aux.ini,&aux.fin);
| |
| 66 | - | V.pb(aux); |
| 66 | + | |
| 67 | aux.type=2; | |
| 68 | - | sort(all(V)); |
| 68 | + | V[i]=aux; |
| 69 | } | |
| 70 | - | set < pair <int,ii> > S; |
| 70 | + | scanf("%d",&M);
|
| 71 | - | set < pair <int,ii> >::iterator it; |
| 71 | + | |
| 72 | - | pair <int,ii> p; |
| 72 | + | |
| 73 | aux.ind=i+1; | |
| 74 | aux.type=1; | |
| 75 | V[N+i]=aux; | |
| 76 | } | |
| 77 | - | clr(use,0); |
| 77 | + | sort(V,V+(N+M)); |
| 78 | ||
| 79 | set < act > S; | |
| 80 | set < act >::iterator it; | |
| 81 | - | FOR(i,V.sz){
|
| 81 | + | act p; |
| 82 | int ans[N]; | |
| 83 | - | p.fst=V[i].fin; |
| 83 | + | |
| 84 | - | p.snd.fst=V[i].ind; |
| 84 | + | FOR(i,M) use[i]=0; |
| 85 | - | p.snd.snd=V[i].cnt; |
| 85 | + | |
| 86 | FOR(i,N+M){
| |
| 87 | if ( V[i].type==1 ){
| |
| 88 | p.fin=V[i].fin; | |
| 89 | - | p.fst=V[i].fin; |
| 89 | + | p.ind=V[i].ind; |
| 90 | - | p.snd.fst=-1; |
| 90 | + | p.cnt=V[i].cnt; |
| 91 | S.insert(p); | |
| 92 | } | |
| 93 | - | ans[V[i].ind-1]=(*it).snd.fst; |
| 93 | + | |
| 94 | - | use[(*it).snd.fst-1]++; |
| 94 | + | p.fin=V[i].fin; |
| 95 | - | if ( use[(*it).snd.fst-1]==(*it).snd.snd ) S.erase(it); |
| 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 | - | puts("YES");
|
| 100 | + | use[p.ind-1]++; |
| 101 | if ( use[p.ind-1]==p.cnt ) S.erase(it); | |
| 102 | } | |
| 103 | - | else puts("NO");
|
| 103 | + | |
| 104 | - | /* |
| 104 | + | |
| 105 | - | FOR(i,V.sz){
|
| 105 | + | |
| 106 | - | cout<<V[i].type<<" "<<V[i].ini<<" "<<V[i].fin<<endl; |
| 106 | + | printf("YES\n")
|
| 107 | - | cout<<endl; |
| 107 | + | |
| 108 | - | }*/ |
| 108 | + | |
| 109 | else printf("NO\n");
| |
| 110 | return 0; | |
| 111 | } |
