梦幻之音的题解有错
2024-02-03 09:49:25
发布于:广东
2阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
void rsolve() {
int nfolder, nemail, windowsz;
cin >> nfolder >> nemail >> windowsz;
vector<int> emailtofolder(nemail);
vector<vector<int>> foldertoemail(nfolder);
vector<vector<int>> filetiming(nfolder);
vector<bool> filed(nemail);
vector<bool> skipped(nemail);
vector<bool> inlinewindow(nemail);
for(int i = 0; i < nemail; i++) {
cin >> emailtofolder[i];
filetiming[max(0, --emailtofolder[i] - windowsz + 1)].push_back(i);
foldertoemail[emailtofolder[i]].push_back(i);
}
int currentemail = 0;
int lhsemail = 0;
int numinwindow = 0;
int rhsemail = nemail-1;
auto fileemail = [&](int id) -> void {
if(inlinewindow[id]) {
inlinewindow[id] = false;
numinwindow--;
}
assert(!filed[id]);
filed[id] = true;
};
int bottom = 0;
for(int i = 0; i < nfolder; i++) {
if(i > bottom && i + windowsz <= nfolder) bottom++;
for(int out: filetiming[i]) if(inlinewindow[out]) fileemail(out);
while(foldertoemail[i].size() && currentemail <= foldertoemail[i].back()) {
if(numinwindow == windowsz) {
while(!inlinewindow[lhsemail]) lhsemail++;
skipped[lhsemail] = true;
inlinewindow[lhsemail] = false;
numinwindow--;
}
if(emailtofolder[currentemail] >= i && emailtofolder[currentemail] <= i + windowsz - 1) {
filed[currentemail++] = true;
continue;
}
inlinewindow[currentemail++] = true; numinwindow++;
}
while(currentemail < nemail && numinwindow < windowsz) {
if(emailtofolder[currentemail] >= i && emailtofolder[currentemail] <= i + windowsz - 1) {
filed[currentemail++] = true;
continue;
}
inlinewindow[currentemail++] = true; numinwindow++;
}
if(currentemail == nemail) {
while(numinwindow < windowsz) {
if(rhsemail < 0) break;
if(!skipped[rhsemail]) {
rhsemail--;
continue;
}
if(emailtofolder[rhsemail] < bottom) {
cout << "NO\n";
return;
}
if(emailtofolder[rhsemail] <= bottom + windowsz - 1) {
filed[rhsemail--] = true;
continue;
}
inlinewindow[rhsemail--] = true; numinwindow++;
}
}
}
for(auto out: filed) {
if(!out) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
void solve() {
int t;
cin >> t;
while(t--) rsolve();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
这里空空如也
有帮助,赞一个