結果
問題 | No.885 アマリクエリ |
ユーザー | chocorusk |
提出日時 | 2019-09-13 21:31:56 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 2,085 bytes |
コンパイル時間 | 1,319 ms |
コンパイル使用メモリ | 102,576 KB |
実行使用メモリ | 10,076 KB |
最終ジャッジ日時 | 2023-09-17 06:58:02 |
合計ジャッジ時間 | 4,689 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 180 ms
9,908 KB |
testcase_01 | AC | 223 ms
9,896 KB |
testcase_02 | AC | 241 ms
9,964 KB |
testcase_03 | AC | 205 ms
10,032 KB |
testcase_04 | AC | 207 ms
10,076 KB |
testcase_05 | AC | 198 ms
9,964 KB |
testcase_06 | AC | 173 ms
10,028 KB |
testcase_07 | AC | 20 ms
10,020 KB |
testcase_08 | AC | 178 ms
4,380 KB |
testcase_09 | AC | 227 ms
10,024 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 4 ms
4,380 KB |
testcase_14 | AC | 3 ms
4,376 KB |
testcase_15 | AC | 4 ms
4,380 KB |
testcase_16 | AC | 4 ms
4,380 KB |
testcase_17 | AC | 4 ms
4,380 KB |
testcase_18 | AC | 4 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 3 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,504 KB |
ソースコード
#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; }