This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int, int>;
void solve()
{
int n, m, q;
cin >> n >> m >> q;
vector<pii> v(m);
vector<int> tmp(1, 0);
for (auto &[a, b] : v)
{
cin >> a >> b;
tmp.emplace_back(a), tmp.emplace_back(b);
}
sort(tmp.begin(), tmp.end());
tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
for (auto &[a, b] : v)
{
a = lower_bound(tmp.begin(), tmp.end(), a) - tmp.begin();
b = lower_bound(tmp.begin(), tmp.end(), b) - tmp.begin();
}
vector<int> lst((int)tmp.size(), -1), day(1, 0);
multiset<pii> st;
for (int i = 0; i < m; ++i)
{
auto [a, b] = v[i];
for (int j = a; j <= b; ++j)
{
if (lst[j] != -1)
st.emplace((day[i] - a) - (day[lst[j]] - v[lst[j]].first), tmp[j] - tmp[j - 1]);
lst[j] = i;
}
day.emplace_back(day.back() + (tmp[b] - tmp[a] + 1));
}
// for (auto [a, b] : st)
// cout << a << ' ' << b << '\n';
vector<pii> qry(q);
for (int i = 0; i < q; ++i)
cin >> qry[i].first, qry[i].second = i;
sort(qry.begin(), qry.end());
// reverse(qry.begin(), qry.end());
vector<int> ans(q);
int sum = 0;
for (pii i : st)
sum += i.second;
for (auto [val, id] : qry)
{
while (!st.empty() && st.begin()->first <= val)
sum -= st.begin()->second, st.erase(st.begin());
ans[id] = sum;
}
for (int i : ans)
cout << i << ' ';
cout << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'void solve()':
Main.cpp:12:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
12 | for (auto &[a, b] : v)
| ^
Main.cpp:19:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
19 | for (auto &[a, b] : v)
| ^
Main.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
29 | auto [a, b] = v[i];
| ^
Main.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for (auto [val, id] : qry)
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |