結果

問題 No.2281 K → K-1 01 Flip
コンテスト
ユーザー lgswdn
提出日時 2023-05-03 15:39:51
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 112 ms / 2,000 ms
コード長 1,449 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,910 ms
コンパイル使用メモリ 192,628 KB
最終ジャッジ日時 2025-02-12 16:38:48
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 56
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:34:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |   scanf("%s",s+1);
      |   ~~~~~^~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

const int N=2e5+9;
int n,m,f[N][22],a[N],p[N][2],lst[2];
char s[N];

int qry(int l,int r) {
  if(l>r) return 0; int g=__lg(r-l+1); 
  return max(f[l][g],f[r-(1<<g)+1][g]);
}

signed main() {
  n=read(), m=read();
  scanf("%s",s+1);
  rep(i,1,n) a[i]=s[i]-'0';
  rep(i,1,n) rep(j,0,1) p[i][j]=p[i-1][j]+(a[i]==j);
  rep(i,1,n) {
    f[i][0]=i-lst[a[i]^1];
    lst[a[i]]=i;
  }
  per(i,n,1)
    rep(h,1,20) if(i+(1<<h)-1<=n)
      f[i][h]=max(f[i][h-1],f[i+(1<<h-1)][h-1]);
  rep(i,1,m) {
    int l=read(), r=read(), k=read(), g=2*k-1;
    int l0=l, r0=r, x=r+1;
    while(l0<=r0) {
      int mid=l0+r0>>1;
      if(p[mid][a[l]^1]!=p[l][a[l]^1]) x=mid,r0=mid-1;
      else l0=mid+1;
    }
    int ml=max(x-l,qry(x,r));
    if(ml<k) {printf("%d\n",r-l+1); continue;}
    int p0=p[r][0]-p[l-1][0], p1=p[r][1]-p[l-1][1];
    int d=((p0-p1)%g+g)%g; if(d<g-d) d=g-d;
    printf("%d\n",d-1);
  }
  return 0;
}
0