#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <climits>
#include <algorithm>
#define int long long
using namespace std;
struct seg{
int l;
int r;
int time;
bool operator<(const seg &a)const{
if(l == a.l){
return r < a.r;
}
return l < a.l;
}
};
// need : inter left
// got : cover all inter right
map<int, int> vals;
set<seg> in;
vector<seg> to_err, to_add;
void compare(seg &a, seg &b){
if(b.l < a.l){
seg c = {b.l, a.l-1, b.time};
to_add.push_back(c);
b.time += a.l - b.l;
b.l = a.l;
}
if(b.r > a.r){
seg c = {a.r + 1, b.r, b.time + a.r - b.l + 1};
to_add.push_back(c);
b.r = a.r;
}
}
signed main(){
int N, Q, M;
cin >> N >> M >> Q;
vector<seg> arr(M);
int day = 0;
for(int i = 0; i < M; i ++){
int a, b;
cin >> a >> b;
arr[i] = {a,b,day};
day += b-a+1;
}
for(int i = 0; i < M; i ++){
seg a = arr[i];
seg t = a;
t.r = INT_MIN;
auto p = in.lower_bound(t);
while((*p).l < a.r && p != in.begin())p--;
while(p != in.end() && (*p).l <= a.r){
seg b = *p;
p++;
if(b.r < a.l)continue;
//cout << " A " << a.l << " " << a.r << " " << a.time << endl;
//cout << " B " << b.l << " " << b.r << " " << b.time << endl;
to_err.push_back(b);
compare(a, b);
//cout << "AD A " << a.l << " " << a.r << " " << a.time << endl;
//cout << "AD B " << b.l << " " << b.r << " " << b.time << endl;
int lmax = max(a.l, b.l);
int rmin = min(a.r, b.r);
int td = b.l - a.l;
vals[a.time + td - b.time - 1] += rmin-lmax+1;
}
for(auto j : to_err){
in.erase(j);
}
to_err.clear();
for(auto j : to_add){
in.insert(j);
}
to_add.clear();
in.insert(a);
}
for(auto i : in){
//cout << "liko " << i.l << " " << i.r << " " << i.time << endl;
}
vector<pair<int, int>> pref;
for(auto[l, r] : vals){
pref.push_back({l, r});
//cout << l <<" " << r << endl;
}
pref.push_back({(int)1e16, 0ll});
for(int i = (int)pref.size()-2; i > -1; i --){
pref[i].second += pref[i+1].second;
}
for(auto[l, r] : pref){
//cout << "P " << l << " " << r << endl;
}
for(int i = 0; i < Q; i ++){
int q;
cin >> q;
cout << (*lower_bound(pref.begin(), pref.end(), make_pair(q, 0ll))).second << " ";
}
cout << endl;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:81:14: warning: variable 'i' set but not used [-Wunused-but-set-variable]
81 | for(auto i : in){
| ^
Main.cpp:93:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
93 | for(auto[l, r] : pref){
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
262 ms |
972 KB |
Output is correct |
| 4 |
Correct |
270 ms |
1384 KB |
Output is correct |
| 5 |
Correct |
601 ms |
30684 KB |
Output is correct |
| 6 |
Correct |
567 ms |
30648 KB |
Output is correct |
| 7 |
Correct |
453 ms |
20916 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
