#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PI; typedef long long LL; typedef double D; #define FI first #define SE second #define MP make_pair #define PB push_back #define R(I,N) for(int I=0;I<N;I++) #define F(I,A,B) for(int I=A;I<B;I++) #define FD(I,N) for(int I=N-1;I>=0;I--) #define make(A) scanf("%d",&A) #define make2(A,B) scanf("%d%d",&A,&B) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) #define db if(1)printf template<typename C> void MA(C& a,C b){if(a<b)a=b;} template<typename C> void MI(C& a,C b){if(a>b)a=b;} #define MAX 1000100 int n,m; int inf = 2e9; vector<pair<int,PI> > d[MAX]; set<int> ak; int il[MAX]; vector<pair<int,PI> > z; void pob(){ make2(n,m);m=0; map<int,int> mapa; R(i,n){ int a,b,sk,k; make2(a,b); make(sk); auto it = mapa.find(sk); if(it == mapa.end()){ k = m; mapa[sk] = m++; }else k = it->SE; d[k].PB({b,MP(a,i)}); z.PB({a,MP(b,k)}); } sort(ALL(z)); } int nn[MAX]; vector<vector<PI>> dp; void rob_drzewko(int i){ sort(ALL(d[i])); nn[i] = 1;while(nn[i] < SZ(d[i]))nn[i]*=2; vector<PI> dp(nn[i]*2,MP(0,0)); R(j,nn[i]){ if(j < SZ(d[i])) dp[j+nn[i]].FI = d[i][j].FI - j; else dp[j+nn[i]].FI = inf; } FD(j,nn[i]) dp[j].FI = min(dp[j*2].FI,dp[j*2+1].FI); ::dp.PB(dp); } void usun_z_drzewka(vector<PI>& dp,int kol,int id){ id += nn[kol]; dp[id] = {inf,0}; while(id > 1){ if((id&1) == 0){ dp[id+1].FI++; dp[id+1].SE++; } id/=2; dp[id].FI = min(dp[id*2].FI,dp[id*2+1].FI) + dp[id].SE; } } int kiedy = inf; multiset<int> se[MAX]; int wyn[MAX]; int wynik; void zajmij(int kol,int kon,int t){ auto x = lower_bound(ALL(d[kol]),MP(kon,MP(-1,-1))); wyn[x->SE.SE] = t; x->SE = {-2,-2}; int id = x - d[kol].begin(); usun_z_drzewka(dp[kol],kol,id); } main(){ pob(); R(i,m)rob_drzewko(i); int t = -1; int i = 0; while(ak.size() != 0 || i != z.size()){ if(t > kiedy){ puts("NIE"); return 0; } if(z.size() != i && z[i].FI <= kiedy){ t = z[i].FI; while(t == z[i].FI){ int kol = z[i].SE.SE; il[kol]++; if(il[kol] == 1){ ak.insert(kol); MI(kiedy,dp[kol][1].FI); } se[kol].insert(z[i].SE.FI); i++; } }else{ t = kiedy; kiedy = inf; wynik++; vector<int> dous; for(int kol:ak){ il[kol]--; auto xxx = se[kol].begin(); int kon = *xxx; se[kol].erase(xxx); zajmij(kol,kon,t); if(il[kol] == 0) dous.PB(kol); else MI(kiedy,dp[kol][1].FI); } for(int kol:dous) ak.erase(kol); } } printf("%d\n",wynik); R(i,n)printf("%d\n",wyn[i]); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | #include<bits/stdc++.h> using namespace std; typedef pair<int,int> PI; typedef long long LL; typedef double D; #define FI first #define SE second #define MP make_pair #define PB push_back #define R(I,N) for(int I=0;I<N;I++) #define F(I,A,B) for(int I=A;I<B;I++) #define FD(I,N) for(int I=N-1;I>=0;I--) #define make(A) scanf("%d",&A) #define make2(A,B) scanf("%d%d",&A,&B) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) #define db if(1)printf template<typename C> void MA(C& a,C b){if(a<b)a=b;} template<typename C> void MI(C& a,C b){if(a>b)a=b;} #define MAX 1000100 int n,m; int inf = 2e9; vector<pair<int,PI> > d[MAX]; set<int> ak; int il[MAX]; vector<pair<int,PI> > z; void pob(){ make2(n,m);m=0; map<int,int> mapa; R(i,n){ int a,b,sk,k; make2(a,b); make(sk); auto it = mapa.find(sk); if(it == mapa.end()){ k = m; mapa[sk] = m++; }else k = it->SE; d[k].PB({b,MP(a,i)}); z.PB({a,MP(b,k)}); } sort(ALL(z)); } int nn[MAX]; vector<vector<PI>> dp; void rob_drzewko(int i){ sort(ALL(d[i])); nn[i] = 1;while(nn[i] < SZ(d[i]))nn[i]*=2; vector<PI> dp(nn[i]*2,MP(0,0)); R(j,nn[i]){ if(j < SZ(d[i])) dp[j+nn[i]].FI = d[i][j].FI - j; else dp[j+nn[i]].FI = inf; } FD(j,nn[i]) dp[j].FI = min(dp[j*2].FI,dp[j*2+1].FI); ::dp.PB(dp); } void usun_z_drzewka(vector<PI>& dp,int kol,int id){ id += nn[kol]; dp[id] = {inf,0}; while(id > 1){ if((id&1) == 0){ dp[id+1].FI++; dp[id+1].SE++; } id/=2; dp[id].FI = min(dp[id*2].FI,dp[id*2+1].FI) + dp[id].SE; } } int kiedy = inf; multiset<int> se[MAX]; int wyn[MAX]; int wynik; void zajmij(int kol,int kon,int t){ auto x = lower_bound(ALL(d[kol]),MP(kon,MP(-1,-1))); wyn[x->SE.SE] = t; x->SE = {-2,-2}; int id = x - d[kol].begin(); usun_z_drzewka(dp[kol],kol,id); } main(){ pob(); R(i,m)rob_drzewko(i); int t = -1; int i = 0; while(ak.size() != 0 || i != z.size()){ if(t > kiedy){ puts("NIE"); return 0; } if(z.size() != i && z[i].FI <= kiedy){ t = z[i].FI; while(t == z[i].FI){ int kol = z[i].SE.SE; il[kol]++; if(il[kol] == 1){ ak.insert(kol); MI(kiedy,dp[kol][1].FI); } se[kol].insert(z[i].SE.FI); i++; } }else{ t = kiedy; kiedy = inf; wynik++; vector<int> dous; for(int kol:ak){ il[kol]--; auto xxx = se[kol].begin(); int kon = *xxx; se[kol].erase(xxx); zajmij(kol,kon,t); if(il[kol] == 0) dous.PB(kol); else MI(kiedy,dp[kol][1].FI); } for(int kol:dous) ak.erase(kol); } } printf("%d\n",wynik); R(i,n)printf("%d\n",wyn[i]); } |