Submission #1285014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285014		okahak71	Addk (eJOI21_addk)	C++20	92 / 100	94 ms	4708 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define all(X) X.begin(), X.end()
#define vec vector
#define ins insert
using namespace std;
#pragma GCC optimize("O3")
const ll inf = 1e18;

map<pll, ll>mp;
ll tim = 0; set<ll>eg;
ll n, m; vec<ll>tin, low;
vec<vec<ll>>g; vec<bool>ch;

void dfs(ll u, ll p){
    ch[u] = 1; bool par_sk = 0;
    tin[u] = low[u] = tim++;
    for(ll v : g[u]){
        if(v == p and !par_sk){
            par_sk = 1;
            continue;
        }
        if(ch[v]) low[u] = min(tin[v], low[u]);
        else{
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > tin[u]){
                ll id = mp[{min(u, v), max(u, v)}];
                if(id) eg.insert(id);
            }
        }
    }
}

void _(){
    ll n, kk; cin >> n >> kk;
    vec<ll>a(n); for(ll &i : a) cin >> i;
    ll q, dum; cin >> q;
    vec<ll>pref(n + 1, 0), qref(n + 1, 0);
    for(ll i = 1; i <= n; i++){
        pref[i] = pref[i - 1] + a[i - 1];
        qref[i] = qref[i - 1] + a[i - 1] * i;
    }
    while(q--){
        ll t; cin >> t;
        if(t == 1) cin >> dum;
        else{
            ll l, r, m; cin >> l >> r >> m;
            ll sz = r - l + 1;
            ll p1, mid, p2, k = min(m, sz - m + 1);
            mid = k * (pref[r - k + 1] - pref[l + k - 2]);
            p1 = (qref[l + k - 2] - qref[l - 1]) - (pref[l + k - 2] - pref[l - 1]) * (l - 1); 
            p2 = (pref[r] - pref[r - k + 1]) * k - ((qref[r] - qref[r - k + 1]) - (pref[r] - pref[r - k + 1]) * (r - k + 1));
            cout << p1 + mid + p2 << endl;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); _();
}

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