Submission #475467

#	Time	Username	Problem	Language	Result	Execution time	Memory
475467		lukameladze	Addk (eJOI21_addk)	C++14	0 / 100	65 ms	1248 KiB

Main

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
int le1,ri1,pr[N],sf[N],pr1[N],a[N],q,n,ty,le,ri,m,ans;
/*void update(int idx, int val,int id) {
     for (int i = idx; i < N; i+=i&(-i)) {
          tree[id][i] += val;
     }
}*/
int getans(int le , int ri) {
     if (le > ri) return 0;
     return pr[ri] - pr[le - 1];
}
int getans1(int le ,int ri) {
     if (le > ri) return 0;
     return (pr1[ri] - pr1[le - 1] - (le-1)*getans(le,ri));
}
int getans2(int le, int ri) {
     if (le > ri) return 0;
     //cout<<le<<" "<<ri<<" "<<sf[le] <<"   "<< sf[ri + 1] <<" "<< (n - (ri + 1)) * getans(le,ri)<<endl;
     return (sf[le] - sf[ri + 1] - (n - ri) * getans(le,ri));
}
main() {
     int k;
     cin>>n>>k;
     for (int i = 1; i <= n; i++) {
          cin>>a[i];
          pr[i] = pr[i-1] + a[i];
          pr1[i] = pr1[i-1] + i*a[i];
        //  update(i,a[i]);
     //     update(i,i*a[i],1);
       //   update(i, (n - i + 1) * a[i],2);
     }
     for (int i = n; i >= 1; i--){
          sf[i] = sf[i+1] + (n - i + 1) * a[i];
     }
     cin>>q;
     while (q -- ) {
          cin>>ty;
          if (ty == 2) {
               cin>>le>>ri>>m;
               if (m == 1) {
                    cout<<getans(le,ri)<<endl;
                    continue;
               }
               //cout<<le<<" "<<ri<<" "<<m<<endl;
               // ri - le + 1 >= m + m
               if (2*m >= ri - le + 1) {
                    ans = m*getans(le + m - 1,ri - m + 1);
                    ans += getans1(le, le + m - 2);
                    ans += getans2(ri - m + 2, ri);
               }
               else {
                    //cout<<"Ss"<<endl;
                    ans = 0;
                    ri1 = ri - m;
                    le1 = le + m;
              
                    ans += getans1(le,ri1);
                    ans += getans2(le1, ri);
                  //  cout<<ans<<endl;
                    ri1++; le1--;
                    ans += (ri1 - le + 1) * getans(ri1,le1);
               }
               cout<<ans<<endl;
               continue;
          }
          cin>>le;
     }
}

Compilation message (stderr)

Main.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main() {
      | ^~~~

• Subtask 1: 0 / 36
• Subtask 2: 0 / 56
• Subtask 3: 0 / 8