oj.uz

Submission #838596

# Submission time Handle Problem Language Result Execution time Memory
838596 2023-08-27T12:35:28 Z otiko_lagadze Addk (eJOI21_addk) C++17
36 / 100
 2000 ms 9400 KB 
/**
 *    author:  otiko_lagadze
 *    created: August 27, 2023 3:33 PM
**/

#include <bits/stdc++.h>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x);
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr <<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << endl;
#else
#define dbg(x...)
#endif

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define answer(x) cout<<x<<endl; return;
#define ll long long
#define pb emplace_back
#define endl '\n'
#define y1 y21
const int inf = 1e9;
const int mxn = 2*1e5+11;
const int lg = 31;
const ll linf = 1e18;
const ll mod = 1e9+7;

vector<ll> t(mxn * 4), a(mxn);
ll n, k;

ll count_seg(ll i, ll l, ll r, ll sz) {
    ll L = max(l, i - sz + 1), R = min(i, r - sz + 1);
    return R - L + 1;
}

void update(ll v, ll tl, ll tr, ll i, ll x) {
    if (tl == tr) {
        a[tl] = x;
        t[v] = x;
        return;
    }

    ll m = (tl + tr) / 2;
    if (i <= m) {
        update(2 * v, tl, m, i, x);
    } else {
        update(2 * v + 1, m + 1, tr, i, x);
    }

    t[v] = t[2 * v] + t[2 * v + 1];
}

ll sum(ll v, ll tl, ll tr, ll l, ll r, ll sz) {
    if (tr < l || tl > r) return 0;
    if (tl == tr) return t[v] * count_seg(tl, l, r, sz);

    ll m = (tl + tr) / 2;
    ll L = sum(2 * v, tl, m, l, r, sz);
    ll R = sum(2 * v + 1, m + 1, tr, l, r, sz);

    return L + R;
}

void run_testcase(){
    cin >> n >> k;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        update(1, 1, n, i, a[i]);
    }

    ll q;
    cin >> q;
    while (q--) {
        ll t;
        cin >> t;

        if (t == 1) {
            ll ind[k];
            for (int i = 0; i < k; i++) {
                cin >> ind[i];
            }
            ll first = ind[0];
            for (int i = 0; i < k - 1; i++) {
                update(1, 1, n, ind[i], a[ind[i + 1]]);
            }
            update(1, 1, n, ind[k - 1], a[first]);
        } else {
            ll l, r, m;
            cin >> l >> r >> m;
            cout << sum(1, 1, n, l, r, m) << endl;
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    ll T = 1;
    while(T--){
        run_testcase();
    }

    return 0;
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 7 ms 8148 KB Output is correct
3 Correct 17 ms 8148 KB Output is correct
4 Correct 32 ms 8148 KB Output is correct
5 Correct 55 ms 8272 KB Output is correct
6 Correct 83 ms 8300 KB Output is correct
7 Correct 116 ms 8312 KB Output is correct
8 Correct 178 ms 8276 KB Output is correct
9 Correct 326 ms 8448 KB Output is correct

Subtask #2
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1268 ms 9032 KB Output is correct
2 Execution timed out 2051 ms 9176 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2051 ms 9400 KB Time limit exceeded
2 Halted 0 ms 0 KB -