QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#363426#7859. BladestormredwhiteWA 273ms6320kbC++173.5kb2024-03-23 22:22:042024-03-23 22:22:05

Judging History

你现在查看的是最新测评结果

  • [2024-03-23 22:22:05]
  • 评测
  • 测评结果:WA
  • 用时:273ms
  • 内存:6320kb
  • [2024-03-23 22:22:04]
  • 提交

answer

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 1e5+23, SQ = 350, lg = 18;
const int SQI = N/SQ;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int t, n, k, cntb, a[N], dp[N], b[N], l[N], r[N], blazy[N], lazy[N];
pii pd[N];
set<int> st;

void updmin(int x) {
	int id = 1;
	while(id <= cntb && r[id] < x) {
		blazy[id] = min(blazy[id], x);
		id++;
	}
	if(id <= cntb) {
		for(int i=l[id]; i<x; i++) lazy[i] = min(lazy[i], x);
	}
}

void solve1() {
	int mxnow = 0;
	for(int i=0; i<=n; i++) st.insert(i);
	for(int i=1; i<=n; i++) {
		mxnow = max(mxnow, a[i]);
		updmin(a[i]);
		for(int j=a[i]-1; j>=0&&j>=a[i]-k; j--) {
			if(st.find(j) == st.end()) break;
			st.erase(j);
			dp[j] = j+k;
		}
		int wh = 0, ans = 0;
		while(wh <= mxnow-1) {
			wh = max(wh+k, min({dp[wh], lazy[wh], blazy[b[wh]]}));
			ans++;
		}
		cout<<ans<<' ';
	}
}

void update(int id) {
	for(int i=r[id]; i>=l[id]; i--) {
		int tp = max(i+k, min(blazy[b[i]], lazy[i]));
		if(tp > r[id]) pd[i] = {tp, 1};
		else pd[i] = Mp(pd[tp].F, pd[tp].S+1);
	}
}

void solve2() {
	int mxnow = 0;
	for(int i=0; i<=n; i++) st.insert(i);
	
	for(int i=1; i<=n; i++) {
		mxnow = max(mxnow, a[i]);
		updmin(a[i]);
		for(int j=a[i]-1; j>=0&&j>=a[i]-k; j--) {
			if(st.find(j) == st.end()) break;
			st.erase(j);
			dp[j] = j+k;
		}
		update(b[a[i]]);
		if(b[a[i]] > 0) update(b[a[i]] - 1);

		int wh = 0, ans = 0;
		while(b[wh] < b[mxnow]) {	
			//cout<<wh<<' '<<pd[wh].F<<' '<<pd[wh].S<<endl;
			ans += pd[wh].S;
			wh = min({pd[wh].F, lazy[l[b[wh]+1]], blazy[b[wh]+1]});
		}
		while(wh < mxnow) {
			ans++;
			wh = max(wh+k, min({dp[wh], lazy[wh], blazy[b[wh]]}));
		}

		//fuck(ans);
		cout<<ans<<' ';
		//if(i == 3) break;
	}
}

void solve() {
	cin>>n>>k;
	for(int i=1; i<=n; i++) {
		//if(i<=3)
		cin>>a[i];
	}
	for(int i=0; i<=n; i+=SQ) {
		cntb++;
		l[cntb] = i, r[cntb] = min(i+SQ-1, n);
		blazy[cntb] = n+1;
		for(int j=i; j<i+SQ&&j<=n; j++) {
			dp[j] = n+1;
			b[j] = cntb;
			lazy[j] = n+1;
			pd[j] = {n+1, 1};
		}
	}
	if(k >= SQ) solve1();
	else solve2();
	st.clear();
	for(int i=0; i<=n+1; i++) {
		cntb = a[i] = dp[i] = b[i] = l[i] = r[i] = blazy[i] = lazy[i] = 0;
		pd[i] = {0, 0};
	}
	cout<<endl;
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>t;
	while(t--) {
		solve();
		//reset();
	}

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5632kb

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: 35ms
memory: 5692kb

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: 96ms
memory: 5728kb

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: 273ms
memory: 5616kb

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: 255ms
memory: 3668kb

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: 205ms
memory: 5692kb

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: 204ms
memory: 3676kb

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: 0
Accepted
time: 166ms
memory: 5740kb

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:

ok 5000 lines

Test #9:

score: -100
Wrong Answer
time: 198ms
memory: 6320kb

input:

50
10000 8
274 974 424 4088 762 1098 5354 5693 8734 243 1673 3993 972 5992 9422 4459 6504 4367 7594 9625 4021 7371 3760 1834 2602 5886 2573 5608 2338 5869 6036 4523 5430 9915 5902 979 6434 6013 8881 9136 7450 6065 9790 9051 9545 9938 8604 7526 5829 2766 1433 6053 9650 1712 5928 9002 3854 1152 2778 1...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 1...

result:

wrong answer 1st lines differ - expected: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...0 1250 1250 1250 1250 1250 1250', found: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 1257 1257 1257 1257 1257 1257 '