Submission #1217404

#TimeUsernameProblemLanguageResultExecution timeMemory
1217404dostsNile (IOI24_nile)C++20
0 / 100
25 ms6852 KiB
#include "nile.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 1e6+1, inf = 4e9; std::vector<long long> calculate_costs(std::vector<signed> W, std::vector<signed> A, std::vector<signed> B, std::vector<signed> E) { int Q = big(E); int N = big(W); vi inds(N); iota(all(inds),0ll); sort(all(inds),[&](int x,int y) {return W[x] < W[y];}); vi benefit(N); int sm = 0; for (int i = 0;i<N;i++) { sm+=A[inds[i]]; benefit[i] = A[inds[i]]-B[inds[i]]; } vi plus,minus; vector<pii> match(N); match[0] = {inf,-inf}; for (int i = 1;i<N;i++) { int d1 = W[inds[i]]-W[inds[i-1]]; if (match[i-1].ff > match[i-1].ss) { match[i] = {d1,inf}; } else { if (d1 > match[i-1].ss) { match[i] = {d1,inf}; } else if (d1 < match[i-1].ff) { match[i] = {d1,match[i-1].ff-1}; } else { match[i] = {match[i-1].ss+1,inf}; } } if (match[i].ff <= match[i-1].ss) { plus.push_back(match[i].ff); minus.push_back(match[i-1].ss+1); } } sort(all(plus)); sort(all(minus)); reverse(all(plus)),reverse(all(minus)); vi R(Q); vector<pii> qs(Q); for (int i = 0;i<Q;i++) qs[i] = {E[i],i}; sort(all(qs)); int cur = 0; for (int i = 0;i<Q;i++) { while (!plus.empty() && plus.back() <= qs[i].ff) { cur++,plus.pop_back(); } while (!minus.empty() && minus.back() <= qs[i].ff) { cur--,minus.pop_back(); } R[qs[i].ss] = sm-2*cur; } return R; }
#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...