QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#718470 | #1700. Redistricting | xw75pyh | 11.111111 | 16ms | 13196kb | C++14 | 1.3kb | 2024-11-06 20:36:28 | 2024-11-06 20:36:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair
#define fr first
#define se second
const int Maxn=2e2+10;
const int Maxm=1e3+10;
const int N=5e5+10;
const int M=2e6+10;
const int mod=998244353;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
}
return x*f;
}
inline void write(int x){
if(x<0){
x=-x;putchar('-');
}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=ans*a%mod;b>>=1;a=a*a%mod;
}
return ans;
}
int n,m;
char a[M];
int sum[M];int f[M];
deque<int>pq;
signed main(){
// freopen("sing.in","r",stdin);
// freopen("sing.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1];
if(a[i]=='H')sum[i]++;
else sum[i]--;
}
pq.pb(0);
for(int i=1;i<=n;i++){
while(!pq.empty()&&i-pq.front()>m)pq.pop_front();
f[i]=f[pq.front()]+(a[i]-a[pq.front()]>=0);
while(!pq.empty()&&(f[pq.back()]>f[i]||(f[pq.back()]==f[i]&&sum[pq.front()]<sum[i])))pq.pop_back();
pq.pb(i);
}
write(f[n]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5.55556
Accepted
time: 0ms
memory: 3580kb
input:
7 2 HGHGGHG
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Wrong Answer
time: 11ms
memory: 12304kb
input:
300000 4000 HHGGHHHHHGHHGHGGHGGGGHGGGHHGHGHHGGGGHGHHGGGHGGHGGGGHHHHHHHHHGGHHGHGHHHHGGHGGHHGGGGHGGHHHGHHHGHHGGGGHHGHHGHGGHGGGGGHGHGHGHHGGGGGGHHHGHGHHHGGHHHGGHHHHHGHGGHGGHHGHGGHGGHHHHGHGHHGHHGGHHGHHHGHHGGHGHGHGGHGHHHHHHGHGHGHGHGGHGGHHHGGHHHGHHGHHGGHHHHHHHHGHHGHGHHGGGGHHGGGGHHHHGGHHGHHGGGGGGHGGGHGGGHHH...
output:
49
result:
wrong answer 1st lines differ - expected: '30', found: '49'
Test #3:
score: 0
Wrong Answer
time: 16ms
memory: 11544kb
input:
300000 5000 HGHGGGGHHHHHHHGGHHHHGHGGGGGGHHHHGGGHHGHGHGHGGGHGGHHGHGGGGHHHHGHHGHGGGGGHGGGGHHGHHGHGGGHHHHHGHHGGHHGHGHHGHHGGGGHGGGHHGHHGGHGGGHHHHGHGGHGGHGGHHGHGHHGGGGHHHGHHGHGGGHHGGGGHGGGHGGGHGHGHHGGHHGHHHHHGHHGGHGGGHGGHHHGHGGGGHHHHHGGHGGGHHGHGGGGGGGHHGGGHGHHGGHHGHHGGGGGGHHHGGGHGGHHGGGGHGHGHGGHGGGHGHGGG...
output:
34
result:
wrong answer 1st lines differ - expected: '46', found: '34'
Test #4:
score: 0
Wrong Answer
time: 7ms
memory: 12136kb
input:
300000 5000 GHGHHGGGGHHGGGHHHGHHHGHGHHHHGGGHHGGGHHGHGHHGHGGHGHHHHGHHGHHGGGGGGHHGGGGHHHGHGGHGHGGGGHGGHGHHHHHHGGHHHGHGGHGGHGGGHGHGHHGHGGHGHGHHHGHGGGHHGHGGGGHHHGHHGHGGHGGHHGHHHGGHHHHHHGGGGGGGHGGGHGHHGGHHHGGHHHGHHHGGHGHGHGGHGHHGHHGHHGGGGHGHGHHHGGHGHGGGHHHGGHHHGHGGGGHHHGHGGHHHGHGHGGHGGHGGHHGGHHHGHHGGHHGG...
output:
45
result:
wrong answer 1st lines differ - expected: '8', found: '45'
Test #5:
score: 0
Wrong Answer
time: 15ms
memory: 12928kb
input:
300000 5000 GHGGHHGGHGHGGHGGHHHGHGHHHHHGHGGGGGGHHGGHGHGGHGGHGGGGHHGGHGGGHHHGHHHHHGHGGHHHGHGHHGHHGGHGGGHHGHHHGHGHHHGGHHHGGHHHGGHHGHHGGHHGGGHHGGGGGGHGGHHGHGHHGHHGHHHHHHHGGHGGHGHGGHHGGGGHGGHHGHGHHGHGHGGGGGHGHGHHHGHHHGGHGGGHGHGHHHGHGHGHGHHGHGGGHHGHGHHGGGHHHGHHGGGGGGHHGHHGGGHGGHHGHHGHHHHHGHGHGGGGGHGHGGHH...
output:
41
result:
wrong answer 1st lines differ - expected: '22', found: '41'
Test #6:
score: 0
Wrong Answer
time: 7ms
memory: 9744kb
input:
300000 10000 HGGHHHGHHHHHGHGGHHGGGGHGHGGHGGGHHHHHGHGHHGHHHGHGHHGHHHGHHHGGHHHHGHHGGGGHGGGGHHGHGGHGGHGGHHHHGGGHGHGGGGGGHGHGGGHGHGGGHGHGHGHGHGGHGGHGHHHHHHGHGGHHHHGGGGGHGGHHGHGHHHGHGHGGHHHGHGGGGGHGHGGGGHHGHHGHHGHHHHGHHHGHGHGGHGHGGHHHGGHHHGGHHHHHHHGHGGHHHGGHGHGGHHHGGHHHGHHHHHGHHHGHHGGGGGGGHHHGGHHHGHGGHGG...
output:
20
result:
wrong answer 1st lines differ - expected: '12', found: '20'
Test #7:
score: 0
Wrong Answer
time: 10ms
memory: 13020kb
input:
300000 20000 HGHHHHHHHHHGHHHHHHHGHHHHGGHHHHHHGHHHGHHHHGHHHHHHHHHHHHHHHHHHHGHHHHHHGGGHHHHHHHHHGGHHHHHHHHHHHHHHHGHHHHHHHHHHHGHHHHHHHHHHGGHHGHHHHHHHHHHHHHHHGHHGGHGHHHGHHHHHHGHHHHHGGHHHHGHHHHHHHHHHHGHHHHHHHHHHGGHHHHHHHHHHHHHGGHHHHHHGHHGHHHHHGHHGHHHHHHHHGHHHHHGHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGGHHHHGHHHHG...
output:
13
result:
wrong answer 1st lines differ - expected: '5', found: '13'
Test #8:
score: 0
Wrong Answer
time: 13ms
memory: 12872kb
input:
300000 20000 HHHHHGGGHHHHHHHHHHHGGHHHHGHGGHHHHHHHHHHHHHGHHHHHHHHHHHGHHHHHGHHHHGHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGHGGHHHHHHHHGHHHHGHHGHHHHHHHGHGGHHHGHHGHHHHHHGGGHHHHHGHHGHHGHHHHGHHHGHHHHHHGGGHHHHHHHHHGHHHHHHHHHHHGHHHHHGHHHGHHHHHHHHHHHGHHHHGGHHGGGHHHGHHGHGGHHHHGHHHHHHHHGHGHHHHHGHHHGHHHHHHGHHHGHHHHGHHGH...
output:
12
result:
wrong answer 1st lines differ - expected: '7', found: '12'
Test #9:
score: 0
Wrong Answer
time: 9ms
memory: 13196kb
input:
300000 20000 GHHHHHHHHHHHHGHHHGHHHHHHGHHHHHHGHGHHHGHHHHHHHHHGHHHHGHHGHHHHHHHHHGHHGHHHGHHHHHHHHHGHGHHHHHHHGHHHHHHHHHHHHHHGHGHHGHHHHHHHHHHGGGHGHHHHGHHHHHHHHHHGHHGGHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHGHHGHHHHHGGHHGHGHHHGHHHGHHHHHGHHHHGHHHHHHGHHHHHHGGHHHHHHHHHHHHGHHHHHGHGHHHGHHGHHGHHGHHHHHHHHHHGHGHHGHHHHHHH...
output:
12
result:
wrong answer 1st lines differ - expected: '6', found: '12'
Test #10:
score: 5.55556
Accepted
time: 15ms
memory: 11964kb
input:
300000 50000 HHGGGGHHGGHHGGHGGHGGGGHGGGGGHHGHGGGHGGHHHGGGHGHGGGHGHGHGGHHGHGHHGGHHGHHGGGGGGHHGGGGGGGGGHHHGHGGGHHGHGGGHHHHHHGGHHHHHHGGHGGGGHGGGHGHHHHHGGHHGGGGHGGHHGGHGHGGHGHHHHGGHHHHGGGHHHHHGGHHHHHGGHGHHHHHGGHHGHGGGGHHGGHGHHHHGHHHHGGHHGHGHHHGGHHGGGGHGHGGHGGGGGHGHGHHGHGGHGGGHGGHGHHHGHGHGHGGGHGGHHHGGGGH...
output:
4
result:
ok single line: '4'
Test #11:
score: 0
Wrong Answer
time: 1ms
memory: 5680kb
input:
1000 20 HHHHHGGGGHHHGHGGHHGGGHGHGHGHGHGGHGGGGHHGGHGGHGGGGHGHHHGGGHGGHHGGGGGGGHGGHGHGGHHHHGHGGGHGGHHHHGHHHGHGHGHHGGGHGGHHHHGHGGHGGHHGHHGHGGHGGGGGGGGGGHGGHHGGHHHHGHHGHGHGHHHGGHGHHHGGGGGGHGGGHGHGGHGHGHHGGHGGHGGGGHHGGHHGHGGHGGHGGGGHGGHGGGGGGGHGHHGHGGHHHHHGHHHGGGHGHGGGHGHHGGHHGGGGHHGHGGGHGGHGGGGHHHGGGGGG...
output:
33
result:
wrong answer 1st lines differ - expected: '28', found: '33'
Test #12:
score: 0
Wrong Answer
time: 1ms
memory: 5604kb
input:
1000 100 GHHHGGGGHHHHGHHHHHHGGHGHGGGHHGGHGGGHHGHHGGHHGHGGGGGGGGGGGHHGHGGHGHHGGHGHGHHGHGGHGHGGHHGGHGHGGGGGGHGHHHHGGHGGHGGGHHHHGGHGGHHHGGHGGHGHGHGHHHHGGGHGGHHHHHGHHGGGGHHGGGGGGHHGGGHGGHGHHGHHGGGGHGGHHGGHHHGGGGGHHGGGGHGGHGGGGHHGGGGHHGGHGHGHGGGGHGHGHHHGGHHHHGGHHGHHHGHGHHGHGGHGGHGHHGHGGGGHHGHGGGHGHGHHHHG...
output:
7
result:
wrong answer 1st lines differ - expected: '6', found: '7'
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 5600kb
input:
1000 200 GGHGGHGGGHGGHHGGHGHHHHGGHGGHHGGGGHHGHGGGHGHHGHGHHGGHHHHHGGHGGGHGGGGGGGGGHGGHGHHGHGHGHGGGGGGGGGGHHHGGHGHHGGGHGGHGGGHGGHGGGHHHGGGGHGHGHGHGGHHHGHGHGGGHGGGHHHGGGHGGGGGGGHHHHHHHHGGHHGGGGGHHHGGGGHHHGGGHGGGGGGHHGHHGGHHGHHGGGHGHGGHGGGHHHHGGHHHGHHGGGHHHHGGGGGHGHHGHHHHHHGGHGGGHGHHHHHHHGGGHHHGGHHHHHGH...
output:
4
result:
wrong answer 1st lines differ - expected: '3', found: '4'
Test #14:
score: 0
Wrong Answer
time: 1ms
memory: 5648kb
input:
1000 300 GGGHHGHGGGGHHGGGHGHGHHGHHHHGHGHGGHGGHGGHHGHGHGHGGHHHHHHHHGGGGHGGHGGGGGGHGGGGHHGHHHHGHGHGGHGHGGGHGHHHGGHHHGHHGGHGGHGHHHGGHGGGGHHHHGHGHHGHGHHHGGGHHGGHGHHGGHGHHHHHGHGGHHHHHHHHGGHHHHHHHGHGHGHHGGHGGHGGGHGHHHGHGHHGHHHGGHHGGHGHGGHHGHHHHGHGGHGGGGHGHHHHHGHGGHHHHGHGGHHHGHHHHGGGHGGHHHGHGGGHHGGGGHHHGHH...
output:
3
result:
wrong answer 1st lines differ - expected: '1', found: '3'
Test #15:
score: 0
Wrong Answer
time: 13ms
memory: 12060kb
input:
300000 50 GGHHHGHGHHGHGGGHGGGHHHGHHHHHGHGGHHGGHGHHHGHHGGHHHGGGHGGGGHHGGGHGGGHGGHHHGGGHHHHGHGGHHHGGHHHHGGGHHHHHGHHHHHGGHHHHGGHHGHGHHGGGHGGGHHGGGGHGGGGHHGHGGGHGGGHHGHGHGGGGGGGHGGHGGGGHGHHHGHGHGHGHHGGGGGGHGHGGHGGGGHGHHGGGGHHHGHHHGGHHGGHGGGGGGHHGHGGHHHGHGHHHHGHGGHHHGGGHGHGHGGHGGHHHHGHHHHGGGGHHHHHHHGHGHG...
output:
4046
result:
wrong answer 1st lines differ - expected: '1542', found: '4046'
Test #16:
score: 0
Wrong Answer
time: 15ms
memory: 12096kb
input:
300000 150 GHGHHGHHGHHGGHHGHHHGHHHGGGHGGHGGHGGGHHHHHHGHHGHGHHGHHGHGHHHGGGHHGHHGHHHHGGGGGHGGGHGHGHHGHHGGGGGHHHHGGHGHHHHHGGGHGGHGHHHHHGGHHGGGHHHGHGGGHHGHGHHGHGHHGHHHHGGHHGHHGHHHGGHGGGHHHHHHHGHGGGHHGGHHHGGHGHGGGGHGGHHGGHHGGGGGHHHGGHGHHHGGHHGGGGHHHHHHGHHHHGGHGHHGHGGGHHGGGHHHHHHGGHHHHHHGHGHHHHHGHGHHGHHGG...
output:
1388
result:
wrong answer 1st lines differ - expected: '482', found: '1388'
Test #17:
score: 0
Wrong Answer
time: 11ms
memory: 9744kb
input:
300000 2000 HHGHHHGGGHGHGGHGGHGHHGHHHGHGGHHHHGHGGGGGGGHGGHHGHGHHHGHGHHHHGHHGGGHHHHGHGGHGHHHHGGHHHGGGGGHHGHHGHGGHGHHHHHHHHGHHHHGHGGGHHGGHHGGHHGGGHGHHGHHHGHGGGGHGHGHHHHHGHHHHHHGHHGHHGHGGHHGHGHGHGHGHGHGGGGHGGHGGGGGGHGGHGHHHGGGHHGHGGGGGGGHHHHHHHGHHGHHGHGGGGGGGHGGGHHGHGHGGHGGHHGGGGHGGGGGGHGHHHHGGHHGGHGGG...
output:
111
result:
wrong answer 1st lines differ - expected: '32', found: '111'
Test #18:
score: 0
Wrong Answer
time: 15ms
memory: 12112kb
input:
300000 2000 HGHHGHHGHHHHGHGHGHHGHHGHHHGGHHGGGGGGHGGHGHHGHGGGGGHHHHGGGGHGGGGGHHHGGHGHHGHHGGGGHGGHGGGHHGHHGGHHGHHGGHGHHHHHHGGHHHHGHHGGGHGHGGHHHGGGGGGHGGHGHGGHGHGGHHGGHHGGHHHHGHGHGGHHHGGGHGGHGGGHGGGGGGGGGGGHGHHHGHHGGGHHHGHGHGHHGGHHHHHGGGGHGHHHHGHGGGHGGHGHHGGHGHHHGHGGHHGHHHHHHHHHHHGHHHHHHHGHGHHGHGGGHHGG...
output:
101
result:
wrong answer 1st lines differ - expected: '47', found: '101'