QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#493012 | #4583. Concerto de Pandemic | PetroTarnavskyi# | WA | 238ms | 63544kb | C++20 | 2.6kb | 2024-07-26 18:32:55 | 2024-07-26 18:32:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int LOG = 18;
const int N = 1 << 18;
int f[N];
int g[LOG][N];
LL cnt[LOG][N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k, p;
cin >> n >> m >> k >> p;
if (p >= k)
{
cout << "0\n";
return 0;
}
VI t(n), fan(n);
while (m--)
{
int c;
cin >> c;
c--;
cin >> t[c];
}
FOR(i, 0, k)
{
int d;
cin >> d;
d--;
fan[d] = 1;
}
vector<LL> dist;
int firstCity = 0;
while (t[firstCity] != 0)
firstCity++;
VI goodCities = {firstCity};
LL sum = 0;
FOR(i, firstCity + 1, n)
{
if (t[i] == 0)
{
dist.PB(i - goodCities.back() + sum);
goodCities.PB(i);
sum = 0;
}
else
sum += t[i];
}
FOR(i, 0, firstCity)
sum += t[i];
dist.PB(sum + n - goodCities.back() + firstCity);
VI nextFan(SZ(goodCities));
int nxtFan = -1;
RFOR(i, SZ(goodCities), 0)
{
int city = goodCities[i];
nextFan[i] = nxtFan;
if (fan[city])
nxtFan = i;
}
FOR(i, 0, SZ(goodCities))
if (nextFan[i] == -1)
nextFan[i] = nxtFan;
LL fullCircle = accumulate(ALL(dist), 0LL);
LL l = 0, r = fullCircle;
while (r - l > 1)
{
LL mid = (l + r) / 2;
int ptr = 0;
LL s = 0;
FOR(i, 0, SZ(goodCities))
{
while (ptr < i || s + dist[ptr % SZ(dist)] <= mid)
{
s += dist[ptr % SZ(dist)];
ptr++;
}
s -= dist[i];
f[i] = ptr % SZ(dist);
}
FOR(i, 0, SZ(goodCities))
{
int concert = f[i];
int distLeft = concert - i;
if (distLeft < 0)
distLeft += SZ(goodCities);
g[0][i] = nextFan[f[concert]];
int distRight = g[0][i] - concert;
if (distRight < 0)
distRight += SZ(goodCities);
cnt[0][i] = distLeft + distRight;
}
FOR(j, 1, LOG)
{
FOR(i, 0, SZ(goodCities))
{
g[j][i] = g[j - 1][g[j - 1][i]];
cnt[j][i] = cnt[j - 1][i] + cnt[j - 1][g[j - 1][i]];
}
}
bool ok = false;
FOR(i, 0, SZ(goodCities))
{
if (!fan[goodCities[i]])
continue;
int curIndex = i;
LL curCnt = 0;
RFOR(j, LOG, 0)
{
if ((p >> j) & 1)
{
curCnt += cnt[j][curIndex];
curIndex = g[j][curIndex];
}
}
if (curCnt >= SZ(goodCities))
{
ok = true;
}
}
if (ok)
r = mid;
else
l = mid;
}
cout << r << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 58912kb
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: 0ms
memory: 3616kb
input:
8 1 3 5 1 5 4 2 7
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 59080kb
input:
5 2 2 1 1 14 2 14 3 5
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
2 1 1 1 1 200000 2
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 133ms
memory: 60020kb
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...
output:
170531
result:
ok single line: '170531'
Test #6:
score: 0
Accepted
time: 238ms
memory: 63544kb
input:
198722 26425 169256 110599 33948 74442 51729 66300 40369 173859 42274 73043 117803 108716 149794 151005 147161 2675 148063 166634 132585 51612 141999 182365 32951 159790 120932 290 82655 150138 49337 10396 171146 129572 33311 193079 195115 171691 180568 77905 65397 110312 156436 149966 9377 55490 12...
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 88ms
memory: 59424kb
input:
200000 150000 50000 24998 187150 200000 81420 200000 167617 200000 100616 200000 135362 200000 156943 200000 83069 200000 48837 200000 179969 200000 138130 200000 133131 200000 196045 200000 169575 200000 163857 200000 106717 200000 191966 200000 131394 200000 145647 200000 160212 200000 75181 20000...
output:
200002
result:
ok single line: '200002'
Test #8:
score: 0
Accepted
time: 77ms
memory: 61268kb
input:
200000 150000 50000 2 99352 200000 85760 200000 126279 200000 78681 200000 191980 200000 123278 200000 90780 200000 183926 200000 92668 200000 92156 200000 157074 200000 104604 200000 87593 200000 183454 200000 38009 200000 132806 200000 96071 200000 135445 200000 123768 200000 80039 200000 199215 2...
output:
1250012500
result:
ok single line: '1250012500'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
200000 199999 1 1 44417 200000 47743 200000 134710 200000 118852 200000 9605 200000 150296 200000 80589 200000 3336 200000 66496 200000 90172 200000 190899 200000 3355 200000 107595 200000 111949 200000 146872 200000 72419 200000 115626 200000 127077 200000 173509 200000 194749 200000 109608 200000 ...
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 145ms
memory: 60792kb
input:
200000 100000 100000 25746 186550 200000 85622 200000 21024 200000 59750 200000 76456 200000 87534 200000 76522 200000 103422 200000 165806 200000 138372 200000 166050 200000 176354 200000 15168 200000 69928 200000 187102 200000 130486 200000 182278 200000 161502 200000 95032 200000 119864 200000 17...
output:
400004
result:
ok single line: '400004'
Test #11:
score: 0
Accepted
time: 15ms
memory: 58180kb
input:
200000 199990 10 9 185044 200000 96615 200000 172973 200000 82849 200000 162889 200000 59668 200000 20522 200000 193263 200000 70559 200000 140931 200000 147680 200000 26312 200000 133330 200000 74332 200000 149589 200000 61277 200000 173461 200000 152403 200000 174666 200000 56706 200000 9288 20000...
output:
3865019326
result:
ok single line: '3865019326'
Test #12:
score: -100
Wrong Answer
time: 18ms
memory: 57988kb
input:
200000 199998 2 1 67932 200000 165398 200000 653 200000 12879 200000 179014 200000 173052 200000 19237 200000 31754 200000 83892 200000 67089 200000 172429 200000 20736 200000 19809 200000 195941 200000 165861 200000 192485 200000 50670 200000 154401 200000 183669 200000 160442 200000 96158 200000 4...
output:
39999800000
result:
wrong answer 1st lines differ - expected: '19999900000', found: '39999800000'