結果
問題 | No.2931 Shibuya 109 |
ユーザー |
|
提出日時 | 2024-10-12 16:13:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 197 ms / 4,000 ms |
コード長 | 1,005 bytes |
コンパイル時間 | 2,070 ms |
コンパイル使用メモリ | 196,956 KB |
最終ジャッジ日時 | 2025-02-24 18:28:19 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 11 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,Q; cin >> N >> Q; vector<int> ones,add(N); for(int i=0; i<N; i++){ int a; cin >> a; if(a == 0) continue; if(a == 9) add.at(i)++; else ones.push_back(i); } int n = ones.size(); vector<int> S1 = ones; for(int i=1; i<n; i++) S1.at(i) += S1.at(i-1); for(int i=1; i<N; i++) add.at(i) += add.at(i-1); while(Q--){ int l,r; cin >> l >> r; l--; r--; int answer = add.at(r); if(l) answer -= add.at(l-1); int l1 = 0,r1 = 0; for(int i=0; i<n; i++){ if(l > ones.at(i)) l1++; if(r >= ones.at(i)) r1++; } if(l1 < r1){ l1--; r1--; answer += (r-l+1)*(r1-l1); answer -= S1.at(r1)+(r1-l1)-l*(r1-l1); if(l1 >= 0) answer += S1.at(l1); } cout << answer << "\n"; } }