oj.uz

Submission #526122

# Submission time Handle Problem Language Result Execution time Memory
526122 2022-02-13T19:18:47 Z speedyArda Addk (eJOI21_addk) C++14
0 / 100
 2000 ms 2436 KB 
#include "bits/stdc++.h"
#define pb push_back
#define vll vector<long long>
#define vb vector<bool>
#define vi vector<int>
#define vs vector<string>
#define vpii vector< pair<int, int> >
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vvi vector< vector<int> > 
#define ld long double
#define mp make_pair
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;
const int MAXN = 1e5;
ll seg[MAXN * 4 + 5], in[MAXN + 5], pref[MAXN + 5];
void build(int v, int l, int r) 
{
    if(l == r)
    {
        seg[v] = in[l];
    } else 
    {
        int m = (l + r) / 2;
        build(2 * v, l, m);
        build(2 * v + 1, m + 1, r); 
        seg[v] = seg[v * 2] + seg[v * 2 + 1];
    }
}

ll sum(int v, int l, int r, int tl, int tr)  
{
    if(tl > tr)
        return 0;
    if(l == tl && r == tr)
        return seg[v];
    int m = (l + r) / 2;
    return sum(2 * v, l, m, tl, min(m, tr)) + sum(2 * v + 1, m + 1, r, max(tl, m + 1), tr);


}

int main() 
{
    FASTIO
    int n, q, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> in[i];
        pref[i] = pref[i - 1];
        pref[i] += in[i];
    }
    build(1, 1, n);
    cin >> q;
    while(q--) 
    {
        int query;
        cin >> query;
        if(query == 1)
        {
            int a;
            cin >> a;
            continue;
        }
        int l, r, m;
        cin >> l >> r >> m;
        ll res = 0;
        int tl = l, tr = r;
        int level = 1;
        while(tl + m - 1 <= r && l + m - 1 <= tr && tl <= tr && level <= m) 
        {
            res += sum(1, 1, n, tl, tr);
            tl++;
            tr--;
            level++;
        }
        if(tl + m - 1 <= r && level <= m)
            res += in[tl];
        if(l + m - 1 <= tr && level <= m)
            res += in[tr];

        cout << res << "\n";
    }
}

Subtask #1
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 25 ms 380 KB Output is correct
3 Correct 99 ms 440 KB Output is correct
4 Correct 231 ms 620 KB Output is correct
5 Correct 410 ms 560 KB Output is correct
6 Correct 690 ms 648 KB Output is correct
7 Correct 979 ms 832 KB Output is correct
8 Correct 1327 ms 836 KB Output is correct
9 Execution timed out 2090 ms 1212 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 56.0

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

Subtask #3
0 / 8.0

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