社区讨论
求调特判
P1712[NOI2016] 区间参与者 1已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mm61nfcv
- 此快照首次捕获于
- 2026/02/28 16:13 上周
- 此快照最后确认于
- 2026/03/02 16:30 上周
95pts,虽然知道要判-1,但就是调不出来。。。(WA on #6)
为了良好的观赏体验,只展示核心部分,如果大佬发现问题在其他部分,踢我
CPP//离散化
vector<int> lsh;
for(int i = 1;i <= n;i++) {
lsh.push_back(a[i].l), lsh.push_back(a[i].r);
}
sort(lsh.begin(), lsh.end());
lsh.erase(unique(lsh.begin(), lsh.end()));
int len = lsh.size() + 1;
for(int i = 1;i <= n;i++) {
a[i].l = lower_bound(lsh.begin(), lsh.end(), a[i].l) - lsh.begin();
a[i].r = lower_bound(lsh.begin(), lsh.end(), a[i].r) - lsh.begin();
}
sort(a + 1, a + n + 1, cmp);
int l = 1, r = 0;
int mn = 1e18;
while(l <= n) {
while(r < l || (r < n && T.range_query(1, 1, len, 1, len) < m)) {
//重合不足m,还没选够,右扩r
r++;
T.range_add(1, 1, len, a[r].l, a[r].r, 1);
}
if(T.range_query(1, 1, len, 1, len) >= m)
mn = min(mn, a[r].len - a[l].len);
//收缩l
T.range_add(1, 1, len, a[l].l, a[l].r, -1);//撤回l区间
l++;
}
cout << (mn == 1e18?-1:mn) << "\n";
回复
共 2 条回复,欢迎继续交流。
正在加载回复...