QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#388087 | #4583. Concerto de Pandemic | kevinyang# | TL | 148ms | 59864kb | C++17 | 1.5kb | 2024-04-13 11:21:30 | 2024-04-13 11:21:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int ln = 18;
int dp[400005][ln];
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,m,k,p;
cin >> n >> m >> k >> p;
vector<int>psa(2*n+2);
vector<int>bad(2*n+2);
for(int i = 0; i<m; i++){
int c,t;
cin >> c >> t;
psa[c] = t;
psa[n+c] = t;
bad[c] = bad[n+c] = 1;
}
for(int i = 1; i<=2*n+1; i++){
psa[i] += psa[i-1]+1;
}
vector<int>good(2*n+2);
for(int i = 1; i<=k; i++){
int x;
cin >> x;
good[x] = 1;
good[x+n] = 1;
}
vector<pair<int,int>>vals;
for(int i = 1; i<=2*n+1; i++){
if(bad[i])continue;
vals.push_back({psa[i],i});
}
int low = -1; int high = (int)1e12;
while(low + 1 < high){
int mid = (low+high)/2;
memset(dp,0,sizeof(dp));
dp[2*n+1][0] = 2*n+1;
for(int i = 2*n; i>=1; i--){
if(good[i]){
auto [sum,idx] = *--lower_bound(vals.begin(),vals.end(),make_pair(psa[i]+mid+1,0LL));
auto [sum2,idx2]= *--lower_bound(vals.begin(),vals.end(),make_pair(sum+mid+1,0LL));
dp[i][0] = min(idx2+1,2*n+1);
}
else{
dp[i][0] = dp[i+1][0];
}
}
for(int j = 1; j<ln; j++){
for(int i = 1; i<=2*n+1; i++){
dp[i][j] = dp[dp[i][j-1]][j-1];
}
}
bool f = false;
for(int i = 1; i<=n; i++){
int x = i;
for(int j = 0; j<ln; j++){
if(p&(1<<j)){
x = dp[x][j];
}
}
if(x>=i+n){
f = true;
}
}
if(f)high = mid;
else low = mid;
}
cout << high << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 141ms
memory: 59864kb
input:
10 4 3 2 1 2 4 4 6 2 7 5 2 5 8
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 144ms
memory: 59804kb
input:
8 1 3 5 1 5 4 2 7
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 138ms
memory: 59864kb
input:
5 2 2 1 1 14 2 14 3 5
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 148ms
memory: 59864kb
input:
2 1 1 1 1 200000 2
output:
0
result:
ok single line: '0'
Test #5:
score: -100
Time Limit Exceeded
input:
190976 113222 55610 23475 51263 120558 10007 171596 46671 108981 117183 169457 18187 84735 149298 124718 79376 129184 28117 76880 109791 87521 114840 59510 38014 178362 41701 11344 27561 192741 173835 54534 71368 76692 122745 95537 152595 158352 43901 162441 98927 105784 22484 96000 19443 113614 370...