oj.uz

답안 #870113

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870113 2023-11-07T01:43:07 Z Cookie Simple (info1cup19_simple) C++14
100 / 100
 293 ms 32844 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("HCN.INP");
ofstream fout("HCN.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
//using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 2e5 + 5, mxq = 2e5 + 5, sq = 350, mxv = 2e6 + 5;
const ll inf = 1e18;
struct Node{
    ll mxodd = -inf, mnodd = inf, mxeven = -inf, mneven = inf;
};
Node st[4 * mxn + 1];
ll lz[4 * mxn + 1], a[mxn + 1];
int n, q;
Node comb(Node a, 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);
}
void push(int nd){
    ll &v = lz[nd];
    if(v & 1){
        swap(st[nd << 1].mxodd, st[nd << 1].mxeven); swap(st[nd << 1 | 1].mxodd, st[nd << 1 | 1].mxeven);
        swap(st[nd << 1].mnodd, st[nd << 1].mneven); swap(st[nd << 1 | 1].mnodd, st[nd << 1 | 1].mneven);
    }
    if(st[nd << 1].mxodd != -inf)st[nd << 1].mxodd += v;
    if(st[nd << 1].mxeven != -inf)st[nd << 1].mxeven += v;
    if(st[nd << 1].mnodd != inf)st[nd << 1].mnodd += v;
    if(st[nd << 1].mneven != inf)st[nd << 1].mneven += v;
    if(st[nd << 1 | 1].mxodd != -inf)st[nd << 1 | 1].mxodd += v;
    if(st[nd << 1 | 1].mxeven != -inf)st[nd << 1 | 1].mxeven += v;
    if(st[nd << 1 | 1].mnodd != inf)st[nd << 1 | 1].mnodd += v;
    if(st[nd << 1 | 1].mneven != inf)st[nd << 1 | 1].mneven += v;
    lz[nd << 1] += v; lz[nd << 1 | 1] += v;
    v = 0;
}
void build(int nd, int l, int r){
    if(l == r){
        if(a[l] & 1){
            st[nd].mxodd = st[nd].mnodd = a[l];
        }else{
            st[nd].mxeven = st[nd].mneven = a[l];
        }
        return;
    }
    int mid = (l + r) >> 1;
    build(nd << 1, l, mid); build(nd << 1 | 1, mid + 1, r);
    st[nd] = comb(st[nd << 1], st[nd << 1 | 1]);
}
void upd(int nd, int l, int r, int ql, int qr, ll v){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        lz[nd] += v;
        if(v & 1){
            swap(st[nd].mxodd, st[nd].mxeven);
            swap(st[nd].mnodd, st[nd].mneven);
        }
        if(st[nd].mxodd != -inf)st[nd].mxodd += v;
        if(st[nd].mxeven != -inf)st[nd].mxeven += v;
        if(st[nd].mnodd != inf)st[nd].mnodd += v;
        if(st[nd].mneven != inf)st[nd].mneven += v;
        return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v);
    st[nd] = comb(st[nd << 1], st[nd << 1 | 1]);
}
Node get(int nd, int l, int r, int ql, int qr){
    if(ql <= l && qr >= r)return(st[nd]);
    int mid = (l + r) >> 1;
    push(nd);
    if(qr <= mid)return(get(nd << 1, l, mid, ql, qr));
    else if(ql > mid)return(get(nd << 1 | 1, mid + 1, r, ql, qr));
    else return(comb(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> a[i];
    build(1, 1, n);
    cin >> q;
    while(q--){
        int idq; cin >> idq;
        if(idq == 0){
            int l, r; ll v; cin >> l >> r >> v;
            upd(1, 1, n, l, r, v);
        }else{
            int l, r; cin >> l >> r;
            Node res = get(1, 1, n, l, r);
            cout << ((res.mneven == inf) ? -1 : res.mneven) << " ";
            cout << ((res.mxodd == -inf) ? -1 : res.mxodd) << "\n";
        }
    }
    return(0);
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 856 KB Output is correct
2 Correct 4 ms 856 KB Output is correct
3 Correct 5 ms 1116 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 5 ms 1112 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 13464 KB Output is correct
2 Correct 267 ms 29412 KB Output is correct
3 Correct 240 ms 31320 KB Output is correct
4 Correct 249 ms 31196 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 856 KB Output is correct
2 Correct 4 ms 856 KB Output is correct
3 Correct 5 ms 1116 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 5 ms 1112 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 106 ms 13464 KB Output is correct
8 Correct 267 ms 29412 KB Output is correct
9 Correct 240 ms 31320 KB Output is correct
10 Correct 249 ms 31196 KB Output is correct
11 Correct 120 ms 16208 KB Output is correct
12 Correct 273 ms 31572 KB Output is correct
13 Correct 293 ms 32316 KB Output is correct
14 Correct 273 ms 31624 KB Output is correct
15 Correct 249 ms 32844 KB Output is correct
16 Correct 73 ms 24656 KB Output is correct