#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 1e18;
multimap<ll, ll> st;
ll L[200200], R[200200], ofs[200200];
vector<array<ll, 2>> S;
void insert(int p, int t){
auto iter = st.insert({ofs[p], t});
auto piter = (iter==st.begin())?iter:prev(iter);
auto niter = next(iter);
if (iter!=st.begin() && niter!=st.end()){
S.push_back({niter->first - piter->first, t - piter->second});
}
if (iter!=st.begin()) piter->second = t;
}
void erase(int p, int t){
auto iter = st.find(ofs[p]);
auto piter = (iter==st.begin())?iter:prev(iter);
auto niter = next(iter);
if (iter!=st.begin()){
S.push_back({iter->first - piter->first, t - piter->second});
piter->second = t;
}
if (niter!=st.end()){
S.push_back({niter->first - iter->first, t - iter->second});
}
st.erase(iter);
}
int main(){
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
vector<array<ll, 3>> E;
ll cur = 1;
for (int i=1;i<=m;i++){
scanf("%lld %lld", L+i, R+i);
E.push_back({L[i], i, 1});
E.push_back({R[i]+1, i, 0});
ofs[i] = -L[i] + cur;
cur += R[i]-L[i]+1;
}
sort(E.begin(), E.end());
int pt = 0;
for (int i=1;i<=n+1;i++){
// printf("i = %d\n", i);
while(pt<(int)E.size() && E[pt][0]==i){
if (E[pt][2]==1) insert(E[pt][1], i);
else erase(E[pt][1], i);
pt++;
// for (auto &[x, y]:st) printf(" %lld %lld\n", x, y);
}
}
S.push_back({-1, 0});
S.push_back({INF, 0});
sort(S.begin(), S.end());
for (int i=1;i<(int)S.size();i++) S[i][1] += S[i-1][1];
while(q--){
ll x;
scanf("%lld", &x);
++x;
auto iter = lower_bound(S.begin(), S.end(), array<ll, 2>{x, 0});
--iter;
ll ans = S.back()[1] - (*iter)[1];
printf("%lld ", ans);
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%lld %lld", L+i, R+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
312 KB |
Output is correct |
8 |
Correct |
1 ms |
312 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
312 KB |
Output is correct |
8 |
Correct |
1 ms |
312 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
43 ms |
1356 KB |
Output is correct |
14 |
Correct |
39 ms |
1356 KB |
Output is correct |
15 |
Correct |
41 ms |
1340 KB |
Output is correct |
16 |
Correct |
46 ms |
1560 KB |
Output is correct |
17 |
Correct |
41 ms |
1296 KB |
Output is correct |
18 |
Correct |
43 ms |
1384 KB |
Output is correct |
19 |
Correct |
45 ms |
1816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
42 ms |
1336 KB |
Output is correct |
4 |
Correct |
46 ms |
1572 KB |
Output is correct |
5 |
Correct |
314 ms |
43416 KB |
Output is correct |
6 |
Correct |
327 ms |
41940 KB |
Output is correct |
7 |
Correct |
214 ms |
27756 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
312 KB |
Output is correct |
8 |
Correct |
1 ms |
312 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
43 ms |
1356 KB |
Output is correct |
14 |
Correct |
39 ms |
1356 KB |
Output is correct |
15 |
Correct |
41 ms |
1340 KB |
Output is correct |
16 |
Correct |
46 ms |
1560 KB |
Output is correct |
17 |
Correct |
41 ms |
1296 KB |
Output is correct |
18 |
Correct |
43 ms |
1384 KB |
Output is correct |
19 |
Correct |
45 ms |
1816 KB |
Output is correct |
20 |
Correct |
51 ms |
2572 KB |
Output is correct |
21 |
Correct |
41 ms |
1860 KB |
Output is correct |
22 |
Correct |
50 ms |
2680 KB |
Output is correct |
23 |
Correct |
39 ms |
1524 KB |
Output is correct |
24 |
Correct |
41 ms |
1208 KB |
Output is correct |
25 |
Correct |
44 ms |
1620 KB |
Output is correct |
26 |
Correct |
49 ms |
2904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
312 KB |
Output is correct |
8 |
Correct |
1 ms |
312 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
43 ms |
1356 KB |
Output is correct |
14 |
Correct |
39 ms |
1356 KB |
Output is correct |
15 |
Correct |
41 ms |
1340 KB |
Output is correct |
16 |
Correct |
46 ms |
1560 KB |
Output is correct |
17 |
Correct |
41 ms |
1296 KB |
Output is correct |
18 |
Correct |
43 ms |
1384 KB |
Output is correct |
19 |
Correct |
45 ms |
1816 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
42 ms |
1336 KB |
Output is correct |
23 |
Correct |
46 ms |
1572 KB |
Output is correct |
24 |
Correct |
314 ms |
43416 KB |
Output is correct |
25 |
Correct |
327 ms |
41940 KB |
Output is correct |
26 |
Correct |
214 ms |
27756 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
51 ms |
2572 KB |
Output is correct |
30 |
Correct |
41 ms |
1860 KB |
Output is correct |
31 |
Correct |
50 ms |
2680 KB |
Output is correct |
32 |
Correct |
39 ms |
1524 KB |
Output is correct |
33 |
Correct |
41 ms |
1208 KB |
Output is correct |
34 |
Correct |
44 ms |
1620 KB |
Output is correct |
35 |
Correct |
49 ms |
2904 KB |
Output is correct |
36 |
Correct |
351 ms |
42340 KB |
Output is correct |
37 |
Correct |
332 ms |
42260 KB |
Output is correct |
38 |
Correct |
329 ms |
42364 KB |
Output is correct |
39 |
Correct |
187 ms |
39220 KB |
Output is correct |
40 |
Correct |
282 ms |
47476 KB |
Output is correct |
41 |
Correct |
251 ms |
47628 KB |
Output is correct |
42 |
Correct |
222 ms |
47580 KB |
Output is correct |
43 |
Correct |
222 ms |
40976 KB |
Output is correct |
44 |
Correct |
212 ms |
39964 KB |
Output is correct |
45 |
Correct |
244 ms |
39224 KB |
Output is correct |
46 |
Correct |
248 ms |
39220 KB |
Output is correct |
47 |
Correct |
215 ms |
39228 KB |
Output is correct |
48 |
Correct |
315 ms |
42584 KB |
Output is correct |