Submission #1238584

#TimeUsernameProblemLanguageResultExecution timeMemory
1238584ricardsjansons나일강 (IOI24_nile)C++20
32 / 100
92 ms12480 KiB
#include "nile.h" #include <bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+5; int p[N]; int root(int i){ return (i==p[i]?i:p[i]=root(p[i])); } vector<ll> calculate_costs(vector<int>w, vector<int>a, vector<int>b, vector<int>e){ int n=w.size(); int q=e.size(); sort(w.begin(),w.end()); map<int,vector<int>>ord; for(int i=0;i<q;i++){ ord[e[i]].push_back(i); } sort(e.begin(),e.end()); int sz[n]; vector<pair<int,int>>g; for(int i=0;i<n;i++){ p[i]=i; if(i){ g.push_back({w[i]-w[i-1],i-1}); } sz[i]=1; } sort(g.begin(),g.end()); vector<ll>res(q); ll cost=2*n; int i=0; for(int d:e){ if(ord[d].empty()){ continue; } while(i<n-1){ auto[x,l]=g[i]; if(x>d){ break; } int r=l+1; l=root(l); r=root(r); if(sz[l]%2&&sz[r]%2){ cost-=2; } sz[l]+=sz[r]; p[r]=l; i++; } for(int j:ord[d]){ res[j]=cost; } ord[d].clear(); } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...