Submission #1177574

#TimeUsernameProblemLanguageResultExecution timeMemory
1177574faqinyeagerStone Arranging 2 (JOI23_ho_t1)C++17
100 / 100
172 ms17280 KiB
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define ub(c, x) distance((c).begin(),lower_bound(c.begin(),c.end(), (x)))
#define N 200015
using namespace std;

const int inf = 1e9;

ll gcd(ll a, ll b){
    if(b == 0) return 1;
    return gcd(b, a % b);
}

ll n, m, s, t, l, k, ans = 0;
vector<pair<ll, ll>> G[N];

vector<ll> dijkstra(ll st){
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<ll> dis;
    dis.resize(n + 1, 1e18);
    dis[st] = 0;
    pq.push({dis[st], st});
    while(!pq.empty()){
        pii now = pq.top();
        pq.pop();
        if(now.first != dis[now.second]) continue;
        for(auto x: G[now.second]){
            ll i = x.first, c = x.second;
            if(dis[i] > now.first + c){
                dis[i] = now.first + c;
                pq.push({dis[i], i});
            }
        }
    }
    return dis;
}

void F(){
    cin >> n >> m >> s >> t >> l >> k;
    rep(i, 0, m){
        ll a, b, c;
        cin >> a >> b >> c;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    vector<ll> dis1 = dijkstra(s);
    vector<ll> dis2 = dijkstra(t);
    vector<ll> dis3 = dis2;

    //for(auto x: dis1) cout << x << ' '; cout << "\n\n";
    //for(auto x: dis2) cout << x << ' '; cout << "\n\n";    

    if(dis1[t] <= k){
        cout << n * (n - 1) / 2 << "\n"; return;
    }
    sort(dis2.begin(), dis2.end());
    rep(i, 1, n + 1){
        ll need = k - dis1[i] - l;
        ll can = upper_bound(dis2.begin(), dis2.end(), need) - dis2.begin();
        ans += can;
        if(dis3[i] <= need) ans--;
    }
    cout << ans << "\n";
}

void Q(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    rep(i, 0, n){
        cin >> a[i];
        mp[a[i]] = i;
    }

    //rep(i, 0, n) cout << b[a[i]] << ' '; cout << "\n";

    int i = 0;
    while(i < n){
        int x = a[i];
        int y = mp[a[i]];
        for(; i <= y; i++) cout << x << ' ';
    }
}

int main() {
    int tc = 1;
    //cin >> tc;
    while(tc--) Q();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...