Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- #include <stack>
- #define forn(i,n) for((i)=0;(i)<(n);(i)++)
- using namespace std;
- long long N,L,C;
- struct elem{
- char type;
- long long index,coor,batt;
- };
- struct kappa{
- long long index, maxd;
- };
- bool operator < (const elem a, const elem b){
- return a.coor<b.coor;
- }
- vector <elem> EL;
- stack <kappa> ST;
- int main()
- {
- long long i,j,k,l,explored=0;
- freopen("B.in","r",stdin);
- scanf("%lld %lld %lld", &N, &L, &C);
- elem aux;
- kappa keepo;
- long long cave[C+5];
- forn(i,N){
- scanf("%lld %lld", &j, &k);
- aux.type='R'; aux.index=i+1; aux.coor=j; aux.batt=k;
- EL.push_back(aux);
- }
- forn(i,C){
- scanf("%lld", &j);
- aux.type='C'; aux.index=i; aux.coor=j; aux.batt=0;
- EL.push_back(aux);
- }
- sort(EL.begin(),EL.end());
- forn(i,EL.size()){
- if(EL[i].type=='R'){
- keepo.index=EL[i].index;
- keepo.maxd=EL[i].coor+EL[i].batt;
- ST.push(keepo);
- }
- else{
- while(!ST.empty()){
- keepo=ST.top();
- if(keepo.maxd>=EL[i].coor){
- cave[ EL[i].index ] = keepo.index;
- explored++;
- break;
- }
- else
- ST.pop();
- }
- if(ST.empty())
- cave[ EL[i].index ]=-1;
- }
- }
- printf("%lld\n",explored);
- forn(i,C)
- printf("%lld\n",cave[i]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement