結果
問題 | No.1000 Point Add and Array Add |
ユーザー | wakannyaai |
提出日時 | 2020-04-24 14:26:20 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 603 ms / 2,000 ms |
コード長 | 7,209 bytes |
コンパイル時間 | 2,022 ms |
コンパイル使用メモリ | 182,536 KB |
実行使用メモリ | 33,920 KB |
最終ジャッジ日時 | 2024-10-15 01:52:20 |
合計ジャッジ時間 | 7,963 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
11,008 KB |
testcase_01 | AC | 6 ms
11,008 KB |
testcase_02 | AC | 5 ms
11,008 KB |
testcase_03 | AC | 6 ms
11,008 KB |
testcase_04 | AC | 5 ms
11,008 KB |
testcase_05 | AC | 5 ms
11,008 KB |
testcase_06 | AC | 6 ms
11,008 KB |
testcase_07 | AC | 5 ms
11,064 KB |
testcase_08 | AC | 6 ms
11,008 KB |
testcase_09 | AC | 5 ms
11,008 KB |
testcase_10 | AC | 5 ms
10,988 KB |
testcase_11 | AC | 5 ms
11,008 KB |
testcase_12 | AC | 8 ms
11,112 KB |
testcase_13 | AC | 7 ms
11,136 KB |
testcase_14 | AC | 9 ms
11,216 KB |
testcase_15 | AC | 8 ms
11,392 KB |
testcase_16 | AC | 406 ms
32,256 KB |
testcase_17 | AC | 356 ms
23,168 KB |
testcase_18 | AC | 586 ms
33,900 KB |
testcase_19 | AC | 590 ms
33,896 KB |
testcase_20 | AC | 392 ms
33,920 KB |
testcase_21 | AC | 603 ms
33,900 KB |
testcase_22 | AC | 458 ms
33,868 KB |
testcase_23 | AC | 603 ms
33,864 KB |
ソースコード
#include "bits/stdc++.h" #include <unordered_set> #define rep(i,n) for(int i = 0; i < n; i++) typedef long long ll; typedef unsigned long long ull; using namespace std; #define vll vector<vector<long long>> #define vl vector<long long> #define vi vector<int> #define vii vector<vector<int>> #define pb push_back #define pf push_front #define ld long double #define Sort(a) sort(a.begin(),a.end()) #define cSort(a,cmp) sort(a.begin(),a.end(),cmp) #define reSort(a) sort(a.rbegin(), a.rend()) static const ll llMAX = numeric_limits<long long>::max(); static const int intMAX = numeric_limits<int>::max(); static const ll llMIN = numeric_limits<long long>::min(); static const int intMIN = numeric_limits<int>::min(); static const ll d_5 = 100000; static const ll d9_7 = 1000000007; static const ll d_9 = 1000000000; static const double PI=3.14159265358979323846; template<class T> T gcd(T a,T b){ if(a==0){ return b; }else if(b==0){ return a; } while(1) { if(a < b) swap(a, b); if(!b) break; a %= b; } return a; } ll digitpower(ll a,ll b){//aのb乗を計算 if(b==1){ return a; }else if(b==0){ return 1; } int mode=0; if(mode==0){ if(b%2==1){ ll tmp = digitpower(a,(b-1)/2); tmp%=d9_7; tmp*=tmp; tmp%=d9_7; tmp*=a; return (tmp)%d9_7; }else{ ll tmp = digitpower(a,(b)/2); tmp%=d9_7; tmp*=tmp; tmp%=d9_7; return (tmp)%d9_7; } }else{ if(b%2==1){ ll tmp = digitpower(a,(b-1)/2); tmp*=tmp; tmp*=a; return (tmp); }else{ ll tmp = digitpower(a,(b)/2); tmp*=tmp; return (tmp); } } return 0; } template<class T> void Printvector(std::vector<T> &a){ int size = a.size(); rep(i,size){ cout<<a[i]<<" "; } cout<<endl; } template<class T> void Printvector(std::vector<std::vector<T>> &a){ int size = a.size(); rep(i,size){ int size2=a[i].size(); rep(j,size2){ cout<<a[i][j]<<" "; } cout<<endl; } cout<<endl; } unordered_set<ll> primes(ll n){ unordered_set<ll> ret; for(ll i=2;i*i<=n;i++){ if(n%i==0){ ret.insert(i); ret.insert(n/i); } } return ret; } long long modinv(long long a, long long m) {//modの逆元 long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } vl facs(1000008,-1); ll Factrial(ll num){ if(facs[num]!=-1){ return facs[num]; } if(num==1||num<=0){ return 1; }else if(num<0){ printf("ERROR_minus\n"); return 0; }else{ facs[num]=(num*Factrial(num-1))%d9_7; return facs[num]; } } struct c{ ll a; ll b; }; template<class T> class delaySegmentTree{ public: int n; vector<T> nodes; vector<T> delaynodes; //constructor delaySegmentTree(int size,T init){ initialize(size,init); } //関数を定義(minなのかmaxなのかとか) T thisoperator(T a, T b){ return a+b; } void update(int x,T a){//xがindex x+=n-1; nodes[x]+=a; while(x>0){ x=(x-1)/2; nodes[x]=thisoperator(nodes[2*x+1],nodes[2*x+2]); } } void initialize(int inputn,T init){ int k=0; while(inputn>(1<<k)){ k++; } n=(1<<k); nodes=vector<T> ((1<<k)*2-1,init); delaynodes=vector<T> ((1<<k)*2-1,init); } // k 番目のノードについて遅延評価を行う void eval(int k, int l, int r) { //kが今見てるindex // 遅延配列が空でない場合、自ノード及び子ノードへの // 値の伝播が起こる if(delaynodes[k] != 0) { nodes[k] += delaynodes[k]; // 最下段かどうかのチェックをしよう // 子ノードは親ノードの 1/2 の範囲であるため、 // 伝播させるときは半分にする if(r - l > 1) { delaynodes[2*k+1] += delaynodes[k] / 2; delaynodes[2*k+2] += delaynodes[k] / 2; } // 伝播が終わったので、自ノードの遅延配列を空にする delaynodes[k] = 0; } } void add(int a, int b, T x, int k=0, int l=0, int r=-1) { if(r < 0) r = n; // k 番目のノードに対して遅延評価を行う eval(k, l, r); // 範囲外なら何もしない if(b <= l || r <= a) return; // 完全に被覆しているならば、遅延配列に値を入れた後に評価 if(a <= l && r <= b) { delaynodes[k] += (r - l) * x; eval(k, l, r); } // そうでないならば、子ノードの値を再帰的に計算して、 // 計算済みの値をもらってくる else { add(a, b, x, 2*k+1, l, (l+r)/2); add(a, b, x, 2*k+2, (l+r)/2, r); nodes[k] = nodes[2*k+1] + nodes[2*k+2]; } } T sec_get(int reql,int reqr,int nowindex=0,int nowl=0,int nowr=-1){ // 最初に呼び出されたときの対象区間は [0, n) //開区間であることに注意 if(nowr < 0) nowr = n; // 要求区間と対象区間が交わらない -> 適当に返す if(nowr <= reql || reqr <= nowl) return 0; //関数が呼び出されるので評価 eval(nowindex,nowl,nowr); // 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う if(reql <= nowl && nowr <= reqr) return nodes[nowindex]; // 要求区間が対象区間の一部を被覆 -> 子について探索を行う // 左側の子を vl ・ 右側の子を vr としている // 新しい対象区間は、現在の対象区間を半分に割ったもの T val1 = sec_get(reql, reqr, 2*nowindex+1, nowl, (nowl+nowr)/2); T val2 = sec_get(reql, reqr, 2*nowindex+2, (nowl+nowr)/2, nowr); return thisoperator(val1, val2); } void Printn(){ cout<<"Printvector"<<endl; rep(i,n){ cout<<nodes[i+n-1]<<" "; } cout<<endl; } }; // 比較関数を定義 bool cmp( const c& left, const c& right ) { return left.b>right.b; } int main(void){ ll n,q; cin>>n>>q; vl a(n); vl x(q),y(q); vector<char> c(q); rep(i,n)cin>>a[i]; rep(i,q){ cin>>c[i]>>x[i]>>y[i]; if(c[i]=='B'){ y[i]--; } x[i]--; } delaySegmentTree<ll> seg1(n,0); delaySegmentTree<ll> seg2(n,0); rep(i,q){ if(c[i]=='A')continue; seg1.add(x[i],y[i]+1,1); } vl ans(n,0); rep(i,q){ if(c[i]=='A'){ ans[x[i]]+=y[i]*(seg1.sec_get(x[i],x[i]+1)-seg2.sec_get(x[i],x[i]+1)); }else{ seg2.add(x[i],y[i]+1,1); } } rep(i,n){ ans[i]+=a[i]*(seg1.sec_get(i,i+1)); } rep(i,n){ cout<<ans[i]<<" "; } cout<<endl; return 0; } //clang++ -g -fsanitize=address -fno-omit-frame-pointer 1.cpp -o test.exe //<<std::setprecision(30) //重複削除 /* std::sort(vec.begin(), vec.end()); vec.erase(std::unique(vec.begin(), vec.end()), vec.end());*/ //ペアの全探索 /*do{ int s=0; for(int i=0;i<n/2;i++)s+=v[i]^v[i+n/2]; r=max(s,r); reverse(v.begin()+n/2,v.end()); }while(next_permutation(v.begin(),v.end()));*/