結果
問題 | No.2735 Demarcation |
ユーザー |
![]() |
提出日時 | 2024-04-19 22:36:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 671 ms / 1,500 ms |
コード長 | 1,290 bytes |
コンパイル時間 | 4,459 ms |
コンパイル使用メモリ | 254,276 KB |
最終ジャッジ日時 | 2025-02-21 04:49:17 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 1000000000000000001int main(){int N;cin>>N;vector<long long> x(N);rep(i,N)cin>>x[i];fenwick_tree<long long> F(N-1);rep(i,N-1){if(x[i]==x[i+1])F.add(i,1);}vector<int> cnt(N+5,0);int Q;cin>>Q;rep(_,Q){long long l,r,S;cin>>l>>r>>S;l--;if(r-l>=100){long long t = F.sum(l,r-1);if(t<=60 && (1LL<<t)<=S){cout<<1<<endl;continue;}else{cout<<0<<endl;continue;}}else{int n = r-l;int ok = 0,ng = n+2;while(ng-ok>1){int mid = (ok+ng)/2;vector<long long> dp(n+1,0);dp[0] = 1;rep(j,n){int C = 0;for(int k=0;k<n;k++){if(j+k>=n)break;if(cnt[x[l+j+k]]==0){C++;if(C>mid)break;cnt[x[l+j+k]] = 1;}dp[j+k+1] = min(S+1,dp[j+k+1]+dp[j]);}for(int k=0;k<n;k++){if(j+k>=n)break;cnt[x[l+j+k]] = 0;}}L:;if(dp.back()>S)ng = mid;else ok = mid;}if(ok>=n)cout<<-1<<endl;else cout<<ok<<endl;}}return 0;}