QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #776440 | #7859. Bladestorm | guodong | WA | 228ms | 3592kb | C++17 | 3.2kb | 2024-11-23 18:41:25 | 2024-11-23 18:41:25 |
Judging History
answer
#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;
Block(int _n){
n = _n;
exist = 0;
ans.resize(_n);
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 < n; ++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;
}
}
}
void add(int x){
exist = 1;
if(mark[x])
return;
mark[x] = 1;
calc();
}
pair<int,int> getAns(int st){
return ans[st];
}
bool Exist(){
return exist;
}
};
signed main()
{
#ifdef NICEGUODONG
freopen("data.in","r",stdin);
#endif
// ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--){
cin >> n >> k;
int len;
if(k * k >= n || n <= 3){
len = n;
}
else{
len = sqrt(n);
}
// 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;
cin >> x;
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].ans[cur - l];
ans += fee;
cur = nxt + l;
}
else{
cur = max(cur + k,block[id].nxt[0] + l);
++ans;
auto &[fee,nxt] = block[id].ans[cur - l];
ans += fee;
cur = nxt + l;
}
++id;
}
cout << ans << " ";
}
cout << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3472kb
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: 128ms
memory: 3592kb
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: -100
Wrong Answer
time: 228ms
memory: 3500kb
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:
wrong answer 527th lines differ - expected: '1 2 3 3 4 4 4 4 4 4', found: '1 2 3 4 4 4 4 4 4 4 '