Submission #1102796

#TimeUsernameProblemLanguageResultExecution timeMemory
1102796PedroBigManNile (IOI24_nile)C++17
38 / 100
67 ms16320 KiB
#include "nile.h" #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <list> #include <iomanip> #include <stdlib.h> #include <time.h> #include <cstring> using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef long double ld; #define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++) #define pb push_back #define mp make_pair #define pl pair<ll,ll> #define ff first #define ss second #define whole(x) x.begin(),x.end() #define DEBUG(i) cout<<"Pedro "<<i<<endl #define INF 1000000000000000000LL #define EPS ((ld)0.00000000001) #define pi ((ld)3.141592653589793) #define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);} ll mod=1000000007; template<class A=ll> void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;} template<class A=ll> void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} vector<ll> extra; class DSU //with range compression and union by subtree size { public: ll N; vector<ll> p,siz; vector<ll> min_value; DSU(ll n) { N=n; REP(i,0,N) {p.pb(i); siz.pb(1); min_value.pb(extra[i]);} } ll find(ll x) { if(p[x]==x) {return x;} ll ans=find(p[x]); p[x]=ans; return ans; } void unionn(ll a, ll b) { a=find(a); b=find(b); if(a==b) {return;} if(siz[a]>siz[b]) {swap(a,b);} p[a]=b; siz[b]+=siz[a]; min_value[b]=min(min_value[a],min_value[b]); } vector<vector<ll> > EquivalenceClasses() //O(N) { vector<vector<ll> > rep; REP(i,0,N) {rep.pb({});} REP(i,0,N) {rep[find(i)].pb(i);} vector<vector<ll> > CC; REP(i,0,N) {if(rep[i].size()>0) {CC.pb(rep[i]);}} return CC; } }; vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) { ll Q = E.size(); ll N = A.size(); vector<pl> a; ll basis = 0LL; REP(i,0,N) {basis+=B[i]; a.pb({W[i],A[i]-B[i]});} sort(whole(a)); REP(i,0,N) {extra.pb(a[i].ss);} DSU X(N); vector<ll> ans(Q,0); vector<pl> queries; REP(q,0,Q) {queries.pb({E[q],q});} sort(whole(queries)); ll D, ind; vector<pl> dist; REP(i,0,N-1) {dist.pb({a[i+1].ff-a[i].ff,i});} sort(whole(dist)); ll dist_ind = 0; ll unite; ll curans = 0LL; REP(i,0,N) {curans+=extra[i];} ll old_extra, new_extra; ll J, K; REP(q,0,Q) { D = queries[q].ff; ind = queries[q].ss; while(dist_ind<N-1 && dist[dist_ind].ff<=D) { unite = dist[dist_ind].ss; J = X.find(unite); K = X.find(unite+1); old_extra = 0LL; if(X.siz[J]%2!=0) {old_extra+=X.min_value[J];} if(X.siz[K]%2!=0) {old_extra+=X.min_value[K];} X.unionn(J,K); J = X.find(J); new_extra=0LL; if(X.siz[J]%2!=0) {new_extra=X.min_value[J];} curans += (new_extra-old_extra); dist_ind++; } ans[ind]=curans+basis; } return ans; }

Compilation message (stderr)

nile.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
nile.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |
#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...