oj.uz

Submission #475471

# Submission time Handle Problem Language Result Execution time Memory
475471 2021-09-22T15:10:36 Z lukameladze Addk (eJOI21_addk) C++14
92 / 100
 312 ms 4852 KB 
# include <bits/stdc++.h>
#define f first
#define int long long
#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;
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;
     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];
     }
     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;
               }
               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 {
                    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

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

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 9 ms 460 KB Output is correct
5 Correct 12 ms 460 KB Output is correct
6 Correct 16 ms 460 KB Output is correct
7 Correct 18 ms 584 KB Output is correct
8 Correct 22 ms 596 KB Output is correct
9 Correct 30 ms 716 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1204 KB Output is correct
2 Correct 90 ms 1588 KB Output is correct
3 Correct 127 ms 2084 KB Output is correct
4 Correct 216 ms 3524 KB Output is correct
5 Correct 312 ms 4852 KB Output is correct
6 Correct 285 ms 4696 KB Output is correct
7 Correct 279 ms 4736 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 1956 KB Output isn't correct
2 Halted 0 ms 0 KB -