結果
問題 | No.885 アマリクエリ |
ユーザー | chocorusk |
提出日時 | 2019-09-13 21:31:56 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 238 ms / 2,000 ms |
コード長 | 2,085 bytes |
コンパイル時間 | 934 ms |
コンパイル使用メモリ | 105,880 KB |
実行使用メモリ | 10,368 KB |
最終ジャッジ日時 | 2024-07-04 03:59:48 |
合計ジャッジ時間 | 4,082 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 180 ms
10,112 KB |
testcase_01 | AC | 223 ms
10,368 KB |
testcase_02 | AC | 238 ms
10,240 KB |
testcase_03 | AC | 201 ms
10,240 KB |
testcase_04 | AC | 205 ms
10,368 KB |
testcase_05 | AC | 201 ms
10,240 KB |
testcase_06 | AC | 168 ms
10,240 KB |
testcase_07 | AC | 21 ms
10,368 KB |
testcase_08 | AC | 177 ms
6,940 KB |
testcase_09 | AC | 229 ms
10,240 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 4 ms
6,948 KB |
testcase_14 | AC | 3 ms
6,940 KB |
testcase_15 | AC | 4 ms
6,944 KB |
testcase_16 | AC | 4 ms
6,940 KB |
testcase_17 | AC | 3 ms
6,940 KB |
testcase_18 | AC | 3 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 4 ms
6,940 KB |
testcase_21 | AC | 2 ms
6,944 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:95:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 95 | for(int i=0; i<n; i++) scanf("%lld", &a[i]); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; int n, sz; vector<ll> mx, sum, lazy; ll a[1<<17]; void init(){ sz=1; while(sz<n) sz<<=1; mx.resize(2*sz-1); sum.resize(2*sz-1); lazy.resize(2*sz-1, -1); for(int i=0; i<n; i++){ mx[i+sz-1]=sum[i+sz-1]=a[i]; } for(int i=sz-2; i>=0; i--){ mx[i]=max(mx[2*i+1], mx[2*i+2]); sum[i]=sum[2*i+1]+sum[2*i+2]; } } void eval(int k, int l, int r){ if(lazy[k]!=-1){ mx[k]=lazy[k]; sum[k]=(r-l)*lazy[k]; if(k<sz-1){ lazy[2*k+1]=lazy[k]; lazy[2*k+2]=lazy[k]; } } lazy[k]=-1; } void update(int a, int b, ll x, int k, int l, int r){ eval(k, l, r); if(r<=a || b<=l) return; if(a<=l && r<=b){ lazy[k]=x; eval(k, l, r); }else{ update(a, b, x, 2*k+1, l, (l+r)/2); update(a, b, x, 2*k+2, (l+r)/2, r); mx[k]=max(mx[2*k+1], mx[2*k+2]); sum[k]=sum[2*k+1]+sum[2*k+2]; } } void update_mod(int a, int b, ll x, int k, int l, int r){ eval(k, l, r); if(r<=a || b<=l || mx[k]<x) return; if(a<=l && r<=b && mx[k]*(r-l)==sum[k]){ lazy[k]=mx[k]%x; eval(k, l, r); }else{ update_mod(a, b, x, 2*k+1, l, (l+r)/2); update_mod(a, b, x, 2*k+2, (l+r)/2, r); mx[k]=max(mx[2*k+1], mx[2*k+2]); sum[k]=sum[2*k+1]+sum[2*k+2]; } } ll sum_query(int a, int b, int k, int l, int r){ eval(k, l, r); if(r<=a || b<=l) return 0; if(a<=l && r<=b) return sum[k]; else return sum_query(a, b, 2*k+1, l, (l+r)/2)+sum_query(a, b, 2*k+2, (l+r)/2, r); } int main() { cin>>n; for(int i=0; i<n; i++) scanf("%lld", &a[i]); init(); int q; cin>>q; for(int i=0; i<q; i++){ ll x; cin>>x; update_mod(0, n, x, 0, 0, sz); printf("%lld\n", sum_query(0, n, 0, 0, sz)); } return 0; }