Submission #1243897

#TimeUsernameProblemLanguageResultExecution timeMemory
1243897somefolkDistributing Candies (IOI21_candies)C++20
11 / 100
5093 ms9032 KiB
#include <iostream> #include <cmath> #include <algorithm> #include <string> #include <vector> #include <map> #include <unordered_map> #include <queue> #include <set> #include <unordered_set> #include <complex> #include <list> #include <cassert> #include <chrono> #include <random> #include <stack> #include <iomanip> #include <fstream> using namespace std; #define endl "\n" // #define int long long const int INF = 1e9+7; const int MOD = 1e9+7; struct Query { int idx, val; }; vector<int> distribute_candies(vector<int> a, vector<int> l, vector<int> r, vector<int> v){ int n = (int)a.size(), q = (int)l.size(); int subtask2 = 1; for(int i = 0; i < q; i++){ if(v[i] < 0){ subtask2 = 0; } } int subtask3 = 1; for(int i = 1; i < n; i++){ if(a[i] != a[i-1]){ subtask3 = 0; } } vector<long long> sol(n, 0); if(subtask3){ vector<Query> qry; for(int i = 0; i < q; i++){ qry.push_back({l[i], v[i]}); qry.push_back({r[i]+1, -v[i]}); } sort(qry.begin(), qry.end(), [&](auto left, auto right){ return left.idx < right.idx; }); // for(auto &i : qry) cout << i.idx << " " << i.val << " | "; // cout << endl; int curr = 0, j = 0; for(int i = 0; i < n; i++){ while(j < n && i == qry[j].idx){ curr += qry[j].val; if(curr > a[i]) curr = a[i]; if(curr < 0) curr = 0; j++; // cout << i << " " << curr << " " << qry[j].idx << " " << qry[j].val << endl; } sol[i] = curr; } } else if(subtask2){ for(int i = 0; i < q; i++){ sol[l[i]] += v[i]; if(r[i] < n-1){ sol[r[i]+1] -= v[i]; } } for(int i = 1; i < n; i++){ sol[i] += sol[i-1]; } } else { for(int i = 0; i < q; i++){ for(int j = l[i]; j <= r[i]; j++){ if(sol[j] >= -v[i] && sol[j] <= a[j]-v[i]){ sol[j] += v[i]; } else { sol[j] = (v[i]>0 ? a[j] : 0); } } } } vector<int> sol2(n, 0); for(int i = 0; i < n; i++){ if(sol[i] > a[i]){ sol2[i] = a[i]; } else { sol2[i] = sol[i]; } } // for(auto &i : sol2){ // cout << i << " "; // } return sol2; }
#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...