oj.uz

Submission #621262

# Submission time Handle Problem Language Result Execution time Memory
621262 2022-08-03T16:06:21 Z Mer123haba456 Addk (eJOI21_addk) C++14
92 / 100
 170 ms 8328 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long double ld;
#define N lli(2e6)
#define MOD lli(1e9 + 7)
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0);
#define heps(v) v.begin(),v.end()
typedef vector<lli> vlli;
typedef pair<lli,lli> plli;
typedef pair<lli,plli> pplli;
typedef vector<plli> vplli;
typedef vector<pplli> vpplli;
typedef map<lli,lli> mlli;

lli t,n,m,k;

string str;

vlli vect;

lli prefart[N];

lli pref[N];

lli sufart[N];

lli suf[N];

int main(){
    fast_io
    cin >> n >> k;
    for(lli i = 0;i<n;i++){
        cin >> t;
        vect.push_back(t);
    }
    for(lli i = 1;i<=n;i++){
        pref[i] = pref[i-1] + vect[i-1];
        prefart[i] = prefart[i-1] + vect[i-1] * i;
    }
    for(lli i = n-1;i>=0;i--){
        suf[i] = suf[i+1] + vect[i];
        sufart[i] = sufart[i+1] + vect[i] * (n - i);
    }
    cin >> t;
    while(t--){
        lli l,r,q;
        cin >> m;
        if(m == 1){
            for(lli i = 0;i<k;i++){
                cin >> q;
            }
        }else{
            cin >> l >> r >> q;
            lli yuk = 2 * q -2;
            lli bas = 0, son = 0;
            lli fa = r - l + 1;
            lli cev = 0;
            if(yuk <= fa){
                bas = q-1;
                son = q-1;
                cev += q * (pref[r-q + 1] - pref[l + q-2]);
            }else{
                lli ort = fa - q + 1;
                cev += ort * (pref[r-ort + 1] - pref[l + ort-2]);
                bas = ort-1;
                son = ort -1;
            }
            bas--;son--;
            lli bsay = 0, ssay = 0;
            if(bas >= 0)
                bsay = (prefart[l + bas] - prefart[l-1]) - (l-1) * (pref[l + bas] - pref[l-1]);
            if(son >= 0)
                ssay = (sufart[r - son -1] - sufart[r]) - (n - r) * (suf[r - son - 1] - suf[r]);
            cev += bsay + ssay;
            //cout << bsay << " " << ssay << endl;
            cout << cev << endl;
        }
    }
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 5 ms 592 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 8 ms 844 KB Output is correct
7 Correct 11 ms 852 KB Output is correct
8 Correct 13 ms 852 KB Output is correct
9 Correct 17 ms 1236 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1476 KB Output is correct
2 Correct 53 ms 2764 KB Output is correct
3 Correct 67 ms 3512 KB Output is correct
4 Correct 111 ms 5932 KB Output is correct
5 Correct 170 ms 8328 KB Output is correct
6 Correct 140 ms 8112 KB Output is correct
7 Correct 168 ms 8096 KB Output is correct

Subtask #3
0 / 8.0

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