[problem](https://codeforces.me/contest/20134/problem/D).↵
↵
Hi everyone, ↵
I’ve been trying to solve [problem](https://codeforces.me/contest/2013/problem/D) D: Minimize the Difference from Codeforces Round 973 (Div. 2). I’ve spent quite a bit of time debugging my code, but I can’t figure out why it’s not working as expected. :(↵
↵
Here’s what I tried to do: ↵
I sorted the input intervals by their start times. ↵
↵
I used a priority queue to keep track of the active intervals within the current window. ↵
↵
As I slide the window from `d` to `n`, I: ↵
↵
-Remove intervals that are no longer in the range. ↵
↵
-Add new intervals that fall within the range. ↵
↵
I kept track of the window with the maximum and minimum number of intervals by checking the size of the priority queue.↵
↵
However, it's giving WA on testcase 2.↵
↵
### Code:↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define sp " "↵
#define newline cout << "\n"↵
#define yes cout << "YES"↵
#define no cout << "NO"↵
#define int long long↵
#define yesif(flag) cout << ((flag) ? "YES" : "NO")↵
#define all(a) a.begin(), a.end()↵
#define pb(a) push_back(a)↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
typedef pair<ll, ll> pll;↵
typedef vector<int> vi;↵
typedef vector<ll> vll;↵
typedef vector<pii> vpii;↵
typedef vector<pll> vpll;↵
typedef map<int, int> mii;↵
typedef map<ll, ll> mll;↵
typedef set<int> si;↵
typedef set<ll> sl;↵
↵
template<typename T> void sort_unique(vector<T> &vec){sort(vec.begin(),vec.end()); vec.resize(unique(vec.begin(),vec.end())-vec.begin());}↵
template<typename T> void scan(vector<T> &v){for(auto &i :v) cin >> i;}↵
template<typename T> void print(vector<T> &v){for(auto &i :v) cout << i << " ";}↵
↵
#ifdef LOCAL↵
#include "debug.h"↵
#else↵
#define bug(...) ↵
#endif↵
↵
void print(priority_queue<pair<int,int>,vector<pair<int, int>>, greater<pair<int, int>>> pq){↵
while(pq.empty() == false) {↵
cout << pq.top().first << " " << pq.top().second << endl; pq.pop();↵
}↵
}↵
void tTestCase() {↵
int t;↵
cin >> t;↵
while (t--) {↵
int n, d, k;↵
cin >> n >> d >> k;↵
vpii points;↵
for (int i = 0; i < k; ++i) {↵
int a, b; cin >> a >> b;↵
points.push_back({a, b});↵
} ↵
sort(all(points));↵
↵
bug(points);↵
priority_queue<pair<int,int>,vector<pair<int, int>>, greater<pair<int, int>>> pq;↵
int indx = 0, res1 = 0, res2 = 0, temp1 = 0, temp2 = INT_MAX ;↵
↵
for (int i = d; i <= n; ++i){↵
↵
while(pq.empty() == false and pq.top().second < (i - d + 1)){↵
// if(!pq.empty())↵
pq.pop();↵
}↵
↵
while(indx < k and points[indx].first <= i and points[indx].second >= (i - d + 1)) {↵
pq.push(points[indx]);↵
indx++;↵
} ↵
↵
int sz = pq.size();↵
bug(sz);↵
if(sz > temp1) {↵
temp1 = sz;↵
res1 = i - d + 1;↵
}↵
if(sz < temp2) {↵
temp2 = sz;↵
res2 = i - d + 1;↵
}↵
↵
}↵
cout << res1 << " " << res2;↵
↵
newline;↵
}↵
}↵
↵
void solve() { ↵
tTestCase(); ↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
solve();↵
↵
return 0;↵
}↵
```↵
↵
If anyone could kindly review my code and point out what I’m doing wrong, I’d be immensely grateful! :)↵
↵
Any feedback or suggestions to improve the implementation or debug this further would mean a lot. Thank you so much in advance for your time and help! ^ ^
↵
Hi everyone, ↵
I’ve been trying to solve [problem](https://codeforces.me/contest/2013/problem/D) D: Minimize the Difference from Codeforces Round 973 (Div. 2). I’ve spent quite a bit of time debugging my code, but I can’t figure out why it’s not working as expected. :(↵
↵
Here’s what I tried to do: ↵
I sorted the input intervals by their start times. ↵
↵
I used a priority queue to keep track of the active intervals within the current window. ↵
↵
As I slide the window from `d` to `n`, I: ↵
↵
-Remove intervals that are no longer in the range. ↵
↵
-Add new intervals that fall within the range. ↵
↵
I kept track of the window with the maximum and minimum number of intervals by checking the size of the priority queue.↵
↵
However, it's giving WA on testcase 2.↵
↵
### Code:↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define sp " "↵
#define newline cout << "\n"↵
#define yes cout << "YES"↵
#define no cout << "NO"↵
#define int long long↵
#define yesif(flag) cout << ((flag) ? "YES" : "NO")↵
#define all(a) a.begin(), a.end()↵
#define pb(a) push_back(a)↵
↵
typedef long long ll;↵
typedef pair<int, int> pii;↵
typedef pair<ll, ll> pll;↵
typedef vector<int> vi;↵
typedef vector<ll> vll;↵
typedef vector<pii> vpii;↵
typedef vector<pll> vpll;↵
typedef map<int, int> mii;↵
typedef map<ll, ll> mll;↵
typedef set<int> si;↵
typedef set<ll> sl;↵
↵
template<typename T> void sort_unique(vector<T> &vec){sort(vec.begin(),vec.end()); vec.resize(unique(vec.begin(),vec.end())-vec.begin());}↵
template<typename T> void scan(vector<T> &v){for(auto &i :v) cin >> i;}↵
template<typename T> void print(vector<T> &v){for(auto &i :v) cout << i << " ";}↵
↵
#ifdef LOCAL↵
#include "debug.h"↵
#else↵
#define bug(...) ↵
#endif↵
↵
void print(priority_queue<pair<int,int>,vector<pair<int, int>>, greater<pair<int, int>>> pq){↵
while(pq.empty() == false) {↵
cout << pq.top().first << " " << pq.top().second << endl; pq.pop();↵
}↵
}↵
void tTestCase() {↵
int t;↵
cin >> t;↵
while (t--) {↵
int n, d, k;↵
cin >> n >> d >> k;↵
vpii points;↵
for (int i = 0; i < k; ++i) {↵
int a, b; cin >> a >> b;↵
points.push_back({a, b});↵
} ↵
sort(all(points));↵
↵
bug(points);↵
priority_queue<pair<int,int>,vector<pair<int, int>>, greater<pair<int, int>>> pq;↵
int indx = 0, res1 = 0, res2 = 0, temp1 = 0, temp2 = INT_MAX ;↵
↵
for (int i = d; i <= n; ++i){↵
↵
while(pq.empty() == false and pq.top().second < (i - d + 1)){↵
// if(!pq.empty())↵
pq.pop();↵
}↵
↵
while(indx < k and points[indx].first <= i and points[indx].second >= (i - d + 1)) {↵
pq.push(points[indx]);↵
indx++;↵
} ↵
↵
int sz = pq.size();↵
bug(sz);↵
if(sz > temp1) {↵
temp1 = sz;↵
res1 = i - d + 1;↵
}↵
if(sz < temp2) {↵
temp2 = sz;↵
res2 = i - d + 1;↵
}↵
↵
}↵
cout << res1 << " " << res2;↵
↵
newline;↵
}↵
}↵
↵
void solve() { ↵
tTestCase(); ↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
solve();↵
↵
return 0;↵
}↵
```↵
↵
If anyone could kindly review my code and point out what I’m doing wrong, I’d be immensely grateful! :)↵
↵
Any feedback or suggestions to improve the implementation or debug this further would mean a lot. Thank you so much in advance for your time and help! ^ ^
