Submission #1148386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148386		KawakiMeido	Circus (Balkan15_CIRCUS)	C++17	0 / 100	24 ms	3748 KiB

circus

/*Author: KawakiMeido*/
#include "circus.h"
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 1e5+10;
const int INF = 1e9+7;
const long long LLINF = 1e18+3;

/*Global Variables*/
int n,m;
int p[N];
int dist[N][2];
vector<int> posl,vall,posr,valr;

void Dijkstra(){
    priority_queue<piii,vector<piii>,greater<piii>> pq;
    for (int i=0; i<n; i++){
        dist[i][0] = INF;
        dist[i][1] = INF;
    }
    dist[n-1][0] = 0;
    dist[n-1][1] = 0;
    pq.push({0,{n-1,0}});
    pq.push({0,{n-1,1}});
    while (!pq.empty()){
        int d = pq.top().fi;
        int u = pq.top().se.fi;
        int dir = pq.top().se.se;
        pq.pop();

        if (d > dist[u][dir]) continue;

//        cout << "cur: " << u << " " << dir << endl;

        /*Create new Ripple*/
        if (!((dist[u][0] == INF)&& (dist[u][1] == INF))){
            int pos,v;

            pos = p[u] - d;
            v = (upper_bound(p,p+n,pos))-p-1;
            if (v>=0 && v<n){
                int delta = abs(p[u] - p[v]);
                if (delta<dist[v][1]){
                    dist[v][1] = delta;
                    pq.push({delta,{v,1}});
                }
            }

            pos = p[u] + d;
            v = (lower_bound(p,p+n,pos)) - p;
            if (v>=0 && v<n){
                int delta = abs(p[u] - p[v]);
                if (delta<dist[v][0]){
                    dist[v][0] = delta;
                    pq.push({delta,{v,0}});
                }
            }
        }

        /*Continue previous Ripple*/
        int v = u;
        if (!dir) ++v;
        else --v;

        if (v>=0 && v<n){
            int delta = abs(p[u] - p[v]);
            if (d+delta<dist[v][dir]){
                dist[v][dir] = d+delta;
                pq.push({d+delta,{v,dir}});
            }
        }
    }
}

void CalcLeft(vector<int> &pos, vector<int>& val){
    vector<pii> query;
    pos.push_back(-INF);
    val.push_back(-INF);
    for (int i=0; i<n; i++){
        int mn = min(dist[i][0],dist[i][1]);
        query.push_back({p[i]+mn,p[i]});
    }
    sort(all(query));
    int idx = 0;
    while (idx!=(int)query.size()){
        int i = query[idx].fi;
        int w = -INF;
        while (idx!=(int)query.size() && query[idx].fi == i){
            w = max(w,query[idx].se);
            ++idx;
        }
        if (w>val.back()){
            pos.push_back(i);
            val.push_back(w);
        }
    }
}

void CalcRight(vector<int> &pos, vector<int>& val){
    vector<pii> query;
    pos.push_back(INF);
    val.push_back(INF);
    for (int i=0; i<n; i++){
        int mn = min(dist[i][0],dist[i][1]);
        query.push_back({p[i]-mn,p[i]});
    }
    sort(all(query),greater<pii>());
    int idx = 0;
    while (idx!=(int)query.size()){
        int i = query[idx].fi;
        int w = INF;
        while (idx!=(int)query.size() && query[idx].fi == i){
            w = min(w,query[idx].se);
            ++idx;
        }
        if (w<val.back()){
            pos.push_back(i);
            val.push_back(w);
        }
    }
    reverse(all(pos));
    reverse(all(val));
}

/*Solution*/
void init(int N, int M, int P[]){
    n = N;
    m = M;
    for (int i=0; i<n; i++){
        p[i] = P[i];
    }

    p[n] = m;
    ++n;

    Dijkstra();

//    for (int i=0; i<n; i++){
//        cout << dist[i][0] << " " << dist[i][1] << endl;
//    }

    CalcLeft(posl,vall);
    CalcRight(posr,valr);
//    cout << "Left:" << endl;
//    for (int idx=0; idx<(int)posl.size(); idx++) cout << posl[idx] << " " << vall[idx] << endl;
//    cout << "Right:" << endl;
//    for (int idx=0; idx<(int)posr.size(); idx++) cout << posr[idx] << " " << valr[idx] << endl;
}

int minLength(int d){
    int ans = INF;
    int pos;
    pos = upper_bound(all(posl),d) - posl.begin()-1;
    ans = min(ans,abs(d-vall[pos]));
    pos = lower_bound(all(posr),d) - posr.begin();
    ans = min(ans,abs(d-valr[pos]));
    return ans;
}

//int q;
//
//void Solve(){
//    cin >> n >> m;
//    for (int i=0; i<n; i++){
//        cin >> p[i];
//    }
//    init(n,m,p);
//    cin >> q;
//    for (int i=1; i<=q; i++){
//        int x; cin >> x;
//        cout << minLength(x) << endl;
//    }
//}
//
///*Driver Code*/
//signed main(){
//    freopen("circus.inp","r",stdin);
//    freopen("circus.out","w",stdout);
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//
//    Solve();
//
//    return 0;
//}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d%d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 scanf("%d", &P[i]);
      |                 ~~~~~^~~~~~~~~~~~~
grader.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
grader.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 scanf("%d", &d);
      |                 ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9