Submission #832507

#TimeUsernameProblemLanguageResultExecution timeMemory
832507_martynasInspections (NOI23_inspections)C++11
29 / 100
2086 ms1048576 KiB
#include <iostream> #include <vector> #include <algorithm> #include <numeric> #include <map> using namespace std; const int mxn = 2e5+5; int n, m, q; int l[mxn], r[mxn], ans[mxn]; long long s[mxn]; int main(int argc, char const *argv[]) { cin >> n >> m >> q; for(int i = 1; i <= m; i++) { cin >> l[i] >> r[i]; } for(int i = 1; i <= q; i++) { cin >> s[i]; } vector<int> order; for(int i = 1; i <= m; i++) { for(int j = l[i]; j <= r[i]; j++) { order.push_back(j); } } map<int, int> last, inc; for(int t = 0; t < (int)order.size(); t++) { if(last.find(order[t]) != last.end()) { inc[t-last[order[t]]-1]++; } last[order[t]] = t; } vector<int> dec_s(q); iota(dec_s.begin(), dec_s.end(), 1); sort(dec_s.begin(), dec_s.end(), [&](int i, int j) { return s[i] > s[j];}); int sum = 0; auto it = inc.rbegin(); for(int i = 0; i < q; i++) { int j = dec_s[i]; while(it != inc.rend() && it->first >= s[j]) { sum += it->second; it++; } ans[j] = sum; } for(int i = 1; i <= q; i++) cout << ans[i] << " "; cout << "\n"; return 0; }
#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...