Submission #59447862 - AtCoder Beginner Contest 378 (original) (raw)

• Top
• Tasks
• Clarifications
• Results
• Standings
• Virtual Standings
• Editorial
• Discuss

Submission #59447862

Source Code Expand

#include #include using namespace std; class seguki{ public: //1index vectornum; int siz=1; void init(int n){ while(siz<n)siz*=2; for (int i=0;i<siz2+1;i++)num.emplace_back(0); } void update(int a,int b){ a=siz+a-1; num[a]=b; //上に更新 a/=2; while(a>=1){ num[a]=num[a2]+num[a2+1]; a/=2; } } //updateじゃなくて加算 void henkou(int a,int b){ a=siz+a-1; num[a]+=b; a/=2; while(a>=1){ num[a]=num[a2]+num[a2+1]; a/=2; } } //a,b半開区間 //sm_num(求めたい区間の半開区間（1~5だったら1,6),1,seguki.siz+1(セルのすべての半開区間）,1(スタート地点のセル１)) int sm_num(int l,int r,int a,int b,int u){ if(r<=a || b<=l)return 0; else if(l<=a && b<=r)return num[u]; int m=(a+b)/2; int L=sm_num(l,r,a,m,u*2); int R=sm_num(l,r,m,b,u*2+1); return L+R; } }; int main() { long long n,m; cin >> n >> m; vectora(n); for(int i=0;i<n;i++)cin >> a[i]; seguki rotti; rotti.init(m); long long cnt=0,cnt2=0,ans=0; for(int i=0;i<n;i++){ cnt2+=cnt; cnt=(cnt+a[i])%m; ans+=cnt(i+1); ans-=cnt2; ans+=rotti.sm_num(cnt+1,m+1,1,rotti.siz+1,1)*m; rotti.henkou(cnt,1); } cout << ans << endl; }

Submission Info

Judge Result