oj.uz

Submission #487352

# Submission time Handle Problem Language Result Execution time Memory
487352 2021-11-15T10:00:48 Z leaked Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 4 ms 2000 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int K=100;
struct segtree{
    vec<int> ids;
    vec<pii>t;
    void build(int v,int t1,int tl,int tr){
        if(tl>tr) return;
        if(tl==tr){
            t[v]={2e9+t1*ids[tl],ids[tl]};
            return;
        }
        int tm=(tl+tr)>>1;
        build(2*v,t1,tl,tm);
        build(2*v+1,t1,tm+1,tr);
        t[v]=max(t[2*v],t[2*v+1]);
    }
    void init(int t1){
        t.resize(sz(ids)*4);
        build(1,t1,0,sz(ids)-1);
    }
    void upd(int id,int x,int v,int tl,int tr){
        if(tl==tr){
            t[v]={x,id};
//            cout<<"UPD "<<id<<' '<<x<<endl;
            return;
        }
        int tm=(tl+tr)>>1;
        if(ids[tm]>=id)
            upd(id,x,2*v,tl,tm);
        else
            upd(id,x,2*v+1,tm+1,tr);
        t[v]=max(t[2*v],t[2*v+1]);
    }
    pii get(int l,int r,int v,int tl,int tr){
        if(ids[tl]>=l&&ids[tr]<=r) return t[v];
        if(ids[tl]>r||ids[tr]<l) return {-2e9,1};
        int tm=(tl+tr)>>1;
        return max(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
    }
}lft[K][K],rgt[K][K];
/// nd+(i-j)<=d1
/// nd+i<=d1+1

void change(int id,int x){
    for(int j=1;j<K;j++){
        lft[j][id%j].upd(id,x+id,1,0,sz(lft[j][id%j].ids)-1);
        rgt[j][id%j].upd(id,x-id,1,0,sz(rgt[j][id%j].ids)-1);
    }
}
signed main(){
    fast_iati;
    int n,m;
    cin>>n>>m;
    vec<int>b(m),p(m);
    vec<vec<int>>have(n,vec<int>());
    for(int i=0;i<m;i++)
        cin>>b[i]>>p[i],have[b[i]].pb(i);
    priority_queue<pii,vec<pii>,greater<pii>>pq;
    for(int t=1;t<K;t++){
        for(int i=0;i<n;i++)
            lft[t][i%t].ids.pb(i),rgt[t][i%t].ids.pb(i);
        for(int j=0;j<t;j++){
            lft[t][j].init(+1),rgt[t][j].init(-1);
        }
    }
    vec<int>dp(n,2e9);
    pq.push({0,b[0]});
    dp[b[0]]=0;
    change(b[0],0);
    while(!pq.empty()){
        int v=pq.top().s;
        int x=pq.top().f;
        pq.pop();
        if(dp[v]!=x) continue;
        for(auto &u : have[v]){
            if(p[u]>=K){
                int j=b[u]-p[u];
                int cnt=1;
                while(j>=0){
                    if(umin(dp[j],dp[v]+cnt))
                        pq.push({dp[j],j}),change(j,dp[j]);
                    j-=p[u];cnt++;
                }
                j=b[u]+p[u];cnt=1;
                while(j<n){
                    if(umin(dp[j],dp[v]+cnt))
                        pq.push({dp[j],j}),change(j,dp[j]);
                    j+=p[u];cnt++;
                }
            }
            else{
                while(1){
                    pii js=lft[p[u]][b[u]%p[u]].get(0,b[u],1,0,sz(lft[p[u]][b[u]%p[u]].ids)-1);
                    int f=js.f,j=js.s;
                    if(dp[v]+v<f){
                        umin(dp[j],dp[v]+(v-j)/p[u]);
                        change(j,dp[j]);
//                        cout<<"NEW "<<j<<' '<<dp[j]<<endl;
                        pq.push({dp[j],j});
                    }
                    else break;
                }
                while(1){
                    pii js=rgt[p[u]][b[u]%p[u]].get(b[u],n-1,1,0,sz(rgt[p[u]][b[u]%p[u]].ids)-1);
                    int f=js.f,j=js.s;
                    if(dp[v]-v<f){
                        umin(dp[j],dp[v]+(j-v)/p[u]);
                        change(j,dp[j]);
//                        cout<<"NEW "<<j<<' '<<dp[j]<<' '<<f<<endl;
                        pq.push({dp[j],j});
                    }
                    else break;
                }
            }
        }
    }
    cout<<(dp[b[1]]==2e9?-1:dp[b[1]]);
    return 0;
}
/*
6 1 3
8 1 2 1 5 4

5 3
0 2
1 1
4 1
dp[v]+(j-v)<=dp[j]
dp[v]-v<=dp[j]-v
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1232 KB Output is correct
2 Correct 1 ms 1232 KB Output is correct
3 Correct 1 ms 1232 KB Output is correct
4 Correct 1 ms 1360 KB Output is correct
5 Correct 1 ms 1360 KB Output is correct
6 Correct 1 ms 1360 KB Output is correct
7 Correct 1 ms 1408 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1232 KB Output is correct
2 Correct 1 ms 1232 KB Output is correct
3 Correct 1 ms 1232 KB Output is correct
4 Correct 1 ms 1360 KB Output is correct
5 Correct 1 ms 1360 KB Output is correct
6 Correct 1 ms 1360 KB Output is correct
7 Correct 1 ms 1360 KB Output is correct
8 Correct 2 ms 1768 KB Output is correct
9 Incorrect 3 ms 2000 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1232 KB Output is correct
2 Correct 1 ms 1232 KB Output is correct
3 Correct 1 ms 1232 KB Output is correct
4 Correct 1 ms 1360 KB Output is correct
5 Correct 1 ms 1360 KB Output is correct
6 Correct 1 ms 1360 KB Output is correct
7 Correct 4 ms 1360 KB Output is correct
8 Correct 2 ms 1744 KB Output is correct
9 Incorrect 2 ms 2000 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1232 KB Output is correct
2 Correct 1 ms 1232 KB Output is correct
3 Correct 1 ms 1232 KB Output is correct
4 Correct 1 ms 1360 KB Output is correct
5 Correct 1 ms 1360 KB Output is correct
6 Correct 2 ms 1360 KB Output is correct
7 Correct 1 ms 1360 KB Output is correct
8 Correct 1 ms 1744 KB Output is correct
9 Incorrect 2 ms 2000 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1232 KB Output is correct
2 Correct 1 ms 1232 KB Output is correct
3 Correct 1 ms 1232 KB Output is correct
4 Correct 1 ms 1360 KB Output is correct
5 Correct 1 ms 1388 KB Output is correct
6 Correct 1 ms 1384 KB Output is correct
7 Correct 1 ms 1360 KB Output is correct
8 Correct 1 ms 1744 KB Output is correct
9 Incorrect 2 ms 1896 KB Output isn't correct
10 Halted 0 ms 0 KB -