oj.uz

Submission #526119

# Submission time Handle Problem Language Result Execution time Memory
526119 2022-02-13T19:05:28 Z speedyArda Addk (eJOI21_addk) C++14
0 / 100
 2000 ms 1856 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];
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];
    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;
        while(tl + m - 1 <= r && l + m - 1 <= tr && tl <= tr) 
        {
            res += sum(1, 1, n, tl, tr);
            tl++;
            tr--;
        }
        if(tl + m - 1 <= r)
            res += in[tl];
        if(l + m - 1 <= tr)
            res += in[tr];
        cout << res << "\n";
    }
}

Subtask #1
0 / 36.0

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

Subtask #2
0 / 56.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 1008 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 2080 ms 1856 KB Time limit exceeded
2 Halted 0 ms 0 KB -