QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #776649 | #7859. Bladestorm | guodong | WA | 106ms | 3980kb | C++17 | 4.9kb | 2024-11-23 19:55:12 | 2024-11-23 19:55:13 |
Judging History
answer
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
int n,k;
class Block{
public:
vector<pair<int,int>> ans;
vector<int> nxt;
vector<int> mark;
int n;
bool exist = 0;
pair<int,int> startv;
Block(int _n){
n = _n;
exist = 0;
ans.resize(k + 1);
nxt.resize(_n);
mark.resize(_n);
}
void calc(){
for(int i = n - 1; i >= 0; --i){
if(mark[i])
nxt[i] = i;
else if(i == n - 1)
nxt[i] = 1e9;
else
nxt[i] = nxt[i + 1];
}
for(int p = 0; p < k; ++p){
int st = p,cnt = 0,flag = 0;
while(1){
if(st == n-1 || nxt[st + 1] == 1e9){
ans[p] = make_pair(cnt,st);
break;
}
if(st + k >= n){
ans[p] = make_pair(cnt + 1,st + k);
break;
}
if(nxt[st + k] == nxt[st + 1]){
st = nxt[st + 1];
}
else{
st = st + k;
}
++cnt;
}
}
int p = nxt[0];
int st = p,cnt = 0,flag = 0;
while(1){
if(st == n-1 || nxt[st + 1] == 1e9){
startv = make_pair(cnt,st);
break;
}
if(st + k >= n){
startv = make_pair(cnt + 1,st + k);
break;
}
if(nxt[st + k] == nxt[st + 1]){
st = nxt[st + 1];
}
else{
st = st + k;
}
++cnt;
}
}
void add(int x){
exist = 1;
if(mark[x])
return;
mark[x] = 1;
calc();
}
pair<int,int> getAns(int st){
if(st == nxt[0]){
return startv;
}
return ans[st];
}
bool Exist(){
return exist;
}
};
inline int gi()
{
char tmp = getchar();
while(!isdigit(tmp)) tmp = getchar();
int ans = 0;
while(isdigit(tmp)){
ans = ans * 10 + tmp - '0';
tmp = getchar();
}
return ans;
}
signed main()
{
#ifdef NICEGUODONG
freopen("data.in","r",stdin);
freopen("wa.out","w",stdout);
#endif
// ios::sync_with_stdio(false);
int T;
T = gi();
while(T--){
n = gi(),k = gi();
int len;
if(k >= 500 && ( k * k >= n || n <= 3)){
set<int> S;
int v = 0;
for(int i = 1; i <= n; ++i){
int x = gi();
S.insert(x);
int cnt = 0;
v = 0;
while(1){
auto it = S.upper_bound(v);
if(it == S.end()){
printf("%d ",cnt);
break;
}
v = max(v + k,*it);
++cnt;
}
}
printf("\n");
len = n;
continue;
}
else{
len = max(k + 4,(int)sqrt(n) + 10);
}
// len = n + 1;
vector<Block> block((n + len - 1) / len + 1, Block(len));
int maxx = 0;
for(int i = 1; i <= n; ++i){
int x;
x = gi();
maxx = max(maxx,x);
block[x / len].add(x % len);
int cur = 0,ans = 0,id = 0,ext = 0;
while(cur < maxx){
int l = id * len;
if(block[id].exist == 0){
++id;
ext = 1;
continue;
}
if(ext == 1){
ext = 0;
ans++;
cur = block[id].nxt[0] + l;
}
if(cur >= l){
auto [fee,nxt] = block[id].getAns(cur - l);
ans += fee;
cur = nxt + l;
}
else{
cur = max(cur + k,block[id].nxt[0] + l);
++ans;
auto t = block[id].getAns(cur - l);
auto &[fee,nxt] = t;
ans += fee;
cur = nxt + l;
}
++id;
}
printf("%d ",ans);
}
printf("\n");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3928kb
input:
3 7 2 4 7 3 6 1 2 5 11 3 10 7 4 9 6 8 5 1 3 2 11 9 2 1 2 3 7 8 9 4 5 6
output:
1 2 3 3 4 4 4 1 2 3 3 3 3 3 4 4 4 4 1 1 2 3 4 4 4 5 5
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 31ms
memory: 3744kb
input:
40319 1 1 1 2 1 1 2 2 1 2 1 2 2 1 2 2 2 2 1 3 1 1 2 3 3 1 1 3 2 3 1 2 1 3 3 1 2 3 1 3 1 3 1 2 3 1 3 2 1 3 2 1 2 3 3 2 1 3 2 3 2 2 1 3 3 2 2 3 1 3 2 3 1 2 3 2 3 2 1 3 3 1 2 3 3 3 1 3 2 3 3 2 1 3 3 3 2 3 1 3 3 3 1 2 3 3 3 2 1 4 1 1 2 3 4 4 1 1 2 4 3 4 1 1 3 2 4 4 1 1 3 4 2 4 1 1 4 2 3 4 1 1 4 3 2 4 1 ...
output:
1 1 2 1 2 1 1 1 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 1 2 2 1 1 2 1 2 2 1 2 2 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4...
result:
ok 40319 lines
Test #3:
score: 0
Accepted
time: 72ms
memory: 3616kb
input:
50000 10 2 9 3 1 10 2 4 6 5 7 8 10 5 8 3 4 1 2 7 5 9 10 6 10 7 6 7 5 9 1 4 10 2 8 3 10 10 3 1 10 2 6 8 9 4 5 7 10 7 8 9 7 5 6 2 1 10 3 4 10 1 7 1 10 8 9 3 4 6 2 5 10 1 6 7 4 10 3 5 8 9 1 2 10 9 4 6 9 7 3 8 5 1 10 2 10 4 2 6 9 3 10 5 1 4 7 8 10 1 7 4 10 3 6 9 2 5 1 8 10 6 9 5 2 3 1 8 10 7 6 4 10 4 3 ...
output:
1 2 3 4 4 4 5 5 5 5 1 2 2 2 2 2 2 2 2 2 1 1 1 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 2 2 1 2 3 3 3 3 3 3 3 3 1 2 3 4 5 6 7 8 9 10 1 2 2 2 2 2 2 2 2 2 1 1 2 2 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
ok 50000 lines
Test #4:
score: 0
Accepted
time: 106ms
memory: 3980kb
input:
5000 100 2 63 78 43 82 37 72 75 31 48 32 69 7 71 5 38 100 85 45 12 83 92 41 81 19 21 14 57 74 87 73 59 4 40 91 55 53 20 60 96 17 64 24 9 22 2 62 84 90 46 61 95 50 26 13 34 79 8 65 54 70 1 56 15 88 67 28 27 98 3 39 51 93 52 11 16 10 97 94 36 18 80 30 66 49 29 42 77 35 99 44 25 68 47 89 33 86 76 23 58...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 22 23 24 25 26 26 27 27 28 29 29 30 31 32 32 33 34 35 36 37 38 39 40 40 40 40 41 41 42 43 44 44 45 46 46 46 46 46 46 46 46 46 47 48 48 49 49 49 49 49 49 49 49 49 49 49 49 49 49 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 1 2 3 4 ...
result:
ok 5000 lines
Test #5:
score: 0
Accepted
time: 103ms
memory: 3696kb
input:
5000 100 3 23 52 62 18 85 78 19 65 26 46 100 33 57 32 3 13 12 16 81 75 72 2 92 22 80 95 60 45 94 24 43 73 67 35 77 15 25 47 56 28 48 36 10 59 93 27 9 34 54 58 55 91 87 31 76 42 11 68 96 97 89 83 79 74 20 8 7 70 38 84 6 64 63 99 53 98 49 66 90 30 69 40 50 61 37 1 39 29 5 4 82 44 41 86 51 14 21 88 17 ...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 17 18 19 20 20 21 21 21 22 23 24 24 24 24 24 25 25 25 25 25 26 26 27 27 27 28 28 28 28 28 28 28 28 28 29 30 30 30 30 30 31 31 31 31 31 31 31 31 32 32 32 33 33 33 33 33 33 33 33 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 1 2 3 4 ...
result:
ok 5000 lines
Test #6:
score: 0
Accepted
time: 82ms
memory: 3792kb
input:
5000 100 8 69 26 68 33 32 41 79 80 22 43 94 31 87 15 7 11 25 4 28 12 13 19 83 48 40 60 76 58 34 81 93 10 55 37 3 59 71 89 49 52 21 82 2 85 84 62 16 45 57 36 39 51 95 50 70 30 42 47 77 64 23 88 1 91 63 61 97 73 67 9 99 53 100 54 18 29 96 72 75 35 98 56 92 46 6 27 65 74 20 86 14 38 78 44 17 66 90 5 8 ...
output:
1 2 3 4 4 5 6 6 7 7 8 8 9 10 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 1 2 3 4 5 6 ...
result:
ok 5000 lines
Test #7:
score: 0
Accepted
time: 84ms
memory: 3700kb
input:
5000 100 8 66 22 6 89 68 15 82 100 62 26 43 79 76 47 32 25 27 33 50 75 77 92 42 40 11 81 54 31 28 7 87 58 96 45 21 91 97 98 13 86 69 19 10 61 72 44 36 24 51 64 55 14 34 46 2 65 59 41 17 5 74 18 57 20 94 3 90 88 78 12 93 8 48 85 37 80 95 9 71 52 83 35 73 56 60 84 39 30 16 49 38 23 1 70 4 53 29 99 63 ...
output:
1 2 3 4 5 6 7 8 8 9 10 11 11 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 1 2 3 4 5...
result:
ok 5000 lines
Test #8:
score: -100
Wrong Answer
time: 105ms
memory: 3800kb
input:
5000 100 8 25 36 39 50 79 40 3 19 91 97 72 6 62 54 33 66 78 26 45 13 43 12 95 94 89 17 70 41 65 52 4 5 21 90 82 68 67 63 83 11 99 57 84 85 98 1 87 74 14 35 31 37 10 30 80 81 60 88 56 32 86 96 53 61 58 71 38 48 55 44 8 24 64 75 9 22 93 34 2 47 100 46 15 23 73 28 76 16 29 49 7 18 51 92 59 77 42 69 20 ...
output:
1 2 3 4 5 5 6 7 8 9 10 10 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 1 2 2 3 3...
result:
wrong answer 48th lines differ - expected: '1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 ...3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3', found: '1 2 2 3 4 4 3 3 3 3 3 3 3 3 3 ... 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 '