社区讨论

求调特判

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 条回复,欢迎继续交流。

正在加载回复...