#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
ll n, m, q, l, r, t;
set<pi> s;
vector<ll> last;
vector<ll> ans;
vector<pi> works;
vector<pi> queries;
vector<ll> answer;
int main()
{
t = 0;
cin >> n >> m >> q;
last.assign(n+5, -1);
ans.assign(q+5,0);
works.resize(m+5);
answer.resize(q);
queries.resize(q);
s.insert(mp(1, n));;
for (ll i=0; i<m; ++i) cin >> works[i].f >> works[i].s;
for (ll i=0; i<q; ++i) {cin >> queries[i].f; queries[i].s = i;}
sort(queries.begin(), queries.end());
for (ll i=0; i<m; ++i)
{
ll midx = LLONG_MAX, midy = LLONG_MIN;
vector<pi> toadd;
ll l = works[i].f, r= works[i].s;
ll time = t+1-l;
auto it = s.ub(mp(l, n+1));
it--;
while (it!=s.end() && (((*it).f<=r && (*it).f>=l) || ((*it).s>=l && (*it).s<=r)))
{
ll x = (*it).f, y= (*it).s;
//show2(x, y);
ll range = min(y, r)-max(x, l)+1;
ll bound = (t+1-l) - last[x];
//show2(range, bound);
auto add = ub(queries.begin(), queries.end(), mp(bound, 0LL))-queries.begin();
if (last[x]!=-1)
{
ans[0]+=range;
ans[add]-=range;
}
if (x<l && y>r)
{
toadd.pb(mp(x, l-1));
toadd.pb(mp(r+1, y));
toadd.pb(mp(l, r));
last[r+1] = last[x];
last[l] = time;
}
else if (x>=l && y<=r) // complete
{
midx = min(midx, x);
midy = max(midy, r);
}
else if (x<l)
{
toadd.pb(mp(x, l-1));
toadd.pb(mp(l, y));
last[l] = time;
}
else if (y>r)
{
toadd.pb(mp(x, r));
toadd.pb(mp(r+1, y));
last[r+1] = last[x];
last[x] = time;
}
it = s.erase(it);
}
for (pi u: toadd) { s.insert(u);}
if (midx!=LLONG_MAX && midy!=LLONG_MAX)
{
s.insert(mp(midx, midy));
last[midx] = time;
}
//for (auto x = s.begin(); x!=s.end(); ++x) show2(x->f, x->s);
t+=r-l+1;
}
for (ll i=0; i<q; ++i)
{
if (i) ans[i]+=ans[i-1];
answer[queries[i].s]=ans[i];
}
for (ll i=0; i<q; ++i) cout << answer[i] << ' ';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
