Submission #338594

#	Time	Username	Problem	Language	Result	Execution time	Memory
338594		bigDuck	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	128 ms	12524 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

/*ifstream fin("test_input.txt");
#define cin fin*/



int t, n, m, k, b[30010], p[30010];
int crd[30010];


int d[30010];
bool v[30010];
vector<pii> g[30010];
bool dog[30010];



void dijkstra(){
multiset<pii> ms;
ms.insert({d[crd[1] ], crd[1]});

while(!ms.empty()){
    auto f=*ms.begin(); ms.erase(ms.begin());
    int nod=f.sc;
    v[nod]=true;
    //cout<<nod<<" "<<d[nod]<<"y\n";
    if(nod==crd[2]){return;}

    for(auto pr:g[nod]){
        int u=pr.ft, c=pr.sc;
        if(v[u]){continue;}
        //cout<<u<<" "<<c<<"x\n";
        auto it=ms.find({d[u], u});
        if(it!=ms.end()){
            ms.erase(it);
            d[u]=min(d[u], d[nod]+c);
            ms.insert({d[u], u});
        }
        else{
                d[u]=d[nod]+c;
            ms.insert({d[u], u} );
        }
    }


}

return;
}




map<pii, int> up, down;
pii pr[30010];



void add_chain1(int b, int p){

int lim=down[{b%p, p}];

for(int i=b-p; (i>=1) && ( (i>=lim) ) ; i-=p){
    if(dog[i]){g[b].pb({i, abs(i-b)/p });  }
}
down[{b%p, p}]=max(lim, b);



}


void add_chain2(int b, int p){



if(up[{b%p, p}]==0){ up[{b%p, p }]=n+1; }
int lim=up[{b%p, p}];

for(int i=b+p; (i<=n) && ( (i<=lim) ) ; i+=p){
    if(dog[i]){g[b].pb({i, abs(i-b)/p }); }
}
up[{b%p, p} ]=min( lim, b);

}





int32_t main(){
INIT
cin>>n>>m;

for(int i=1; i<=n; i++){d[i]=-1; }

for(int i=1; i<=m; i++){
cin>>b[i]>>p[i]; b[i]++;
crd[i ]=b[i];
dog[b[i] ]=true;
pr[i]={b[i], p[i]};
}
sort(pr+1, pr+1+m);
for(int i=1; i<=m; i++){
    add_chain1(pr[i].ft, pr[i].sc);
}

for(int i=m; i>=1; i--){
    add_chain2(pr[i].ft, pr[i].sc);
}




d[crd[1] ]=0;
dijkstra();
cout<<d[crd[2] ];

/*for(int i=1; i<=n; i++){
    for(auto u:g[i]){
        cout<<u.ft<<" ";
    }
    cout<<"\n";
}*/



return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43