oj.uz

Submission #962472

# Submission time Handle Problem Language Result Execution time Memory
962472 2024-04-13T15:44:39 Z Whisper Simple (info1cup19_simple) C++17
100 / 100
 365 ms 43328 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
const int MAX = 2e5 + 5;
int nArr, numQuery;
int a[MAX];

struct Node{
    int mxodd, mxeven, mnodd, mneven;
    Node(): mxodd(-1), mxeven(-1), mnodd(LINF), mneven(LINF){}
    Node(int _mxodd, int _mxeven, int _mnodd, int _mneven){
        mxodd = _mxodd;
        mxeven = _mxeven;
        mnodd = _mnodd;
        mneven = _mneven;
    }
    friend Node operator + (const Node& a, const Node& b){
        Node res;
        res.mxodd = max(a.mxodd, b.mxodd);
        res.mnodd = min(a.mnodd, b.mnodd);
        res.mxeven = max(a.mxeven, b.mxeven);
        res.mneven = min(a.mneven, b.mneven);
        return res;
    }
};

Node f[MAX << 2];
int lz[MAX << 2];
void BuildTree(int id, int l, int r){
    if (l == r){
        if(a[l] & 1)
            f[id].mxodd = a[l], f[id].mnodd = a[l];
        else
            f[id].mxeven = a[l], f[id].mneven = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    BuildTree(id << 1, l, mid);
    BuildTree(id << 1 | 1, mid + 1, r);
    f[id] = f[id << 1] + f[id << 1 | 1];
}
void pushDown(int id){
    if(!lz[id]) return;
    for (auto &i : {2 * id, 2 * id + 1}){
        if(f[i].mxodd != -1) f[i].mxodd += lz[id];
        if(f[i].mxeven != -1) f[i].mxeven += lz[id];
        if(f[i].mnodd != LINF) f[i].mnodd += lz[id];
        if(f[i].mneven != LINF) f[i].mneven += lz[id];
        lz[i] += lz[id];
    }
    if (lz[id] & 1){
        swap(f[id << 1].mxodd, f[id << 1].mxeven);
        swap(f[id << 1].mnodd, f[id << 1].mneven);
        swap(f[id << 1 | 1].mxodd, f[id << 1 | 1].mxeven);
        swap(f[id << 1 | 1].mnodd, f[id << 1 | 1].mneven);
    }
    lz[id] = 0;
}
void modify(int id, int l, int r, int u, int v, int val){
    if (u > r || v < l) return;
    if (u <= l && v >= r){
        if (f[id].mxodd != -1) f[id].mxodd += val;
        if (f[id].mxeven != -1) f[id].mxeven += val;
        if (f[id].mnodd != LINF) f[id].mnodd += val;
        if (f[id].mneven != LINF) f[id].mneven += val;
        lz[id] += val;
        if (val & 1){
            swap(f[id].mxodd, f[id].mxeven);
            swap(f[id].mnodd, f[id].mneven);
        }
        return;
    }
    pushDown(id);
    int mid = (l + r) >> 1;
    modify(id << 1, l, mid, u, v, val);
    modify(id << 1 | 1, mid + 1, r, u, v, val);
    f[id] = f[id << 1] + f[id << 1 | 1];
}

Node Query(int id, int l, int r, int u, int v){
    if (u > r || v < l) return Node();
    if (u <= l && v >= r) return f[id];
    pushDown(id);
    int mid = (l + r) >> 1;
    Node ql = Query(id << 1, l, mid, u, v);
    Node qr = Query(id << 1 | 1, mid + 1, r, u, v);
    return (ql + qr);
}
void Whisper(){
    cin >> nArr;
    for (int i = 1; i <= nArr; ++i) cin >> a[i];
    BuildTree(1, 1, nArr);
    cin >> numQuery;
    for (int i = 1; i <= numQuery; ++i){
        int cmd; cin >> cmd;
        if(cmd == 0){
            int l, r, val; cin >> l >> r >> val;
            modify(1, 1, nArr, l, r, val);
        }
        else{
            int l, r; cin >> l >> r;
            Node ans = Query(1, 1, nArr, l, r);
            cout << (ans.mneven == LINF ? -1 : ans.mneven) << " " << ans.mxodd << '\n';
        }
    }
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27480 KB Output is correct
2 Correct 9 ms 27480 KB Output is correct
3 Correct 11 ms 27484 KB Output is correct
4 Correct 12 ms 27736 KB Output is correct
5 Correct 9 ms 27740 KB Output is correct
6 Correct 9 ms 27740 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 29848 KB Output is correct
2 Correct 223 ms 32504 KB Output is correct
3 Correct 216 ms 32476 KB Output is correct
4 Correct 190 ms 32340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27480 KB Output is correct
2 Correct 9 ms 27480 KB Output is correct
3 Correct 11 ms 27484 KB Output is correct
4 Correct 12 ms 27736 KB Output is correct
5 Correct 9 ms 27740 KB Output is correct
6 Correct 9 ms 27740 KB Output is correct
7 Correct 98 ms 29848 KB Output is correct
8 Correct 223 ms 32504 KB Output is correct
9 Correct 216 ms 32476 KB Output is correct
10 Correct 190 ms 32340 KB Output is correct
11 Correct 125 ms 34900 KB Output is correct
12 Correct 365 ms 42040 KB Output is correct
13 Correct 262 ms 42832 KB Output is correct
14 Correct 301 ms 42124 KB Output is correct
15 Correct 245 ms 43328 KB Output is correct
16 Correct 66 ms 35404 KB Output is correct