oj.uz

Submission #962473

# Submission time Handle Problem Language Result Execution time Memory
962473 2024-04-13T15:45:25 Z vjudge1 Simple (info1cup19_simple) C++17
100 / 100
 302 ms 37968 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 27484 KB Output is correct
2 Correct 9 ms 27484 KB Output is correct
3 Correct 11 ms 27616 KB Output is correct
4 Correct 9 ms 27736 KB Output is correct
5 Correct 9 ms 27736 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 91 ms 30032 KB Output is correct
2 Correct 187 ms 32356 KB Output is correct
3 Correct 187 ms 32340 KB Output is correct
4 Correct 214 ms 32600 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27484 KB Output is correct
2 Correct 9 ms 27484 KB Output is correct
3 Correct 11 ms 27616 KB Output is correct
4 Correct 9 ms 27736 KB Output is correct
5 Correct 9 ms 27736 KB Output is correct
6 Correct 9 ms 27740 KB Output is correct
7 Correct 91 ms 30032 KB Output is correct
8 Correct 187 ms 32356 KB Output is correct
9 Correct 187 ms 32340 KB Output is correct
10 Correct 214 ms 32600 KB Output is correct
11 Correct 129 ms 32080 KB Output is correct
12 Correct 302 ms 36176 KB Output is correct
13 Correct 256 ms 37124 KB Output is correct
14 Correct 283 ms 36180 KB Output is correct
15 Correct 240 ms 37968 KB Output is correct
16 Correct 68 ms 29020 KB Output is correct