QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #776630 | #7859. Bladestorm | guodong | WA | 92ms | 3584kb | C++17 | 4.6kb | 2024-11-23 19:47:13 | 2024-11-23 19:47: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;
}
};
signed main()
{
#ifdef NICEGUODONG
freopen("data.in","r",stdin);
// freopen("wa.out","w",stdout);
#endif
ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--){
cin >> n >> k;
int len;
if( k * k >= n || n <= 3){
set<int> S;
int v = 0;
for(int i = 1; i <= n; ++i){
int x;
cin >> x;
S.insert(x);
int cnt = 0;
while(1){
auto it = S.upper_bound(v);
if(it == S.end()){
cout << cnt << " ";
break;
}
v = max(v + k,*it);
++cnt;
}
}
cout << '\n';
len = n;
continue;
}
else{
len = sqrt(n) + k + 1;
}
// 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].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;
}
cout << ans << " ";
}
cout << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
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: -100
Wrong Answer
time: 92ms
memory: 3496kb
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 1 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 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:
wrong answer 2nd lines differ - expected: '1 2', found: '1 1 '