Submission #1243660

#TimeUsernameProblemLanguageResultExecution timeMemory
1243660QuentolosseDistributing Candies (IOI21_candies)C++20
0 / 100
5093 ms15260 KiB
#include "candies.h" #include <bits/stdc++.h> using namespace std; #define int long long vector<signed> distribute_candies(vector<signed> c, vector<signed> l, vector<signed> r, vector<signed> v) { int n = c.size(); int q = l.size(); vector<pair<int,int>> inter; for (int i = 0; i < q; i++) { inter.push_back(make_pair(l[i], i)); inter.push_back(make_pair(r[i]+1, i)); } sort(inter.begin(), inter.end()); vector<int> hauteurs(q+1); int i_inter = 0; vector<signed> rep(n); for (int i = 0; i < n; i++) { while(inter[i_inter].first <= i) { int val = 0; int j = inter[i_inter].second; if (inter[i_inter].first == l[j]) { val = v[j]; } else { val = -v[j]; } for (int k = j; k <= q; k++) { hauteurs[k] += val; } i_inter++; } int mini = 1e9; int maxi = -1e9; int pos_min = -1; int pos_max = -1; int pos = -1; for (int j = q - 1; j >= 0; j--) { if (hauteurs[j] < mini) { mini = hauteurs[j]; pos_min = j; } if (hauteurs[j] > maxi) { maxi = hauteurs[j]; pos_max = j; } if (maxi - mini >= c[i]) { if (j == pos_min) { pos = pos_max; } else { pos = pos_min; } break; } } if (pos == -1) { if (mini >= 0 && maxi <= c[i]) { rep[i] = hauteurs[q]; } else if (mini < 0) { pos = pos_min; } else if (maxi > c[i]) { pos = pos_max; } } if (pos == pos_max) { rep[i] = c[i] - (hauteurs[pos] - hauteurs[q]); } else { rep[i] = hauteurs[q] - hauteurs[pos]; } } return rep; }
#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...