oj.uz

답안 #690930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
690930 2023-01-30T16:46:18 Z divad Simple (info1cup19_simple) C++14
100 / 100
 307 ms 41776 KB 
#include <iostream>
#define int long long
#define lc (nod<<1)
#define rc ((nod<<1)|1)
#define INF (1ULL<<60)
#define MAX 200002
using namespace std;
int n,q,t,x,y,v,mini,maxi;

struct Nod{
    int maximp = -1;
    int minimp = INF;
    int maxpar = -1;
    int minpar = INF;
    int lazy;
} aint[4*MAX];

void merge(int nod){
    aint[nod].maximp = max(aint[lc].maximp, aint[rc].maximp);
    aint[nod].minimp = min(aint[lc].minimp, aint[rc].minimp);
    aint[nod].maxpar = max(aint[lc].maxpar, aint[rc].maxpar);
    aint[nod].minpar = min(aint[lc].minpar, aint[rc].minpar);
}

void change(int nod, int val){
    if(aint[nod].maximp != -1){
        aint[nod].maximp += val;
        aint[nod].minimp += val;
    }
    if(aint[nod].maxpar != -1){
        aint[nod].maxpar += val;
        aint[nod].minpar += val;
    }
    if(val%2 == 0){
    }else{
        swap(aint[nod].maxpar, aint[nod].maximp);
        swap(aint[nod].minpar, aint[nod].minimp);
    }
}

void propag(int nod){
    if(aint[nod].lazy != 0){
        aint[lc].lazy += aint[nod].lazy;
        change(lc, aint[nod].lazy);
        aint[rc].lazy += aint[nod].lazy;
        change(rc, aint[nod].lazy);
        aint[nod].lazy = 0;
    }
}

void build(int nod, int st, int dr){
    if(st == dr){
        cin >> x;
        if(x%2 == 0){
            aint[nod].maxpar = aint[nod].minpar = x;
        }else{
            aint[nod].maximp = aint[nod].minimp = x;
        }
    }else{
        int mid = ((st+dr)>>1);
        build(lc, st, mid);
        build(rc, mid+1, dr);
        merge(nod);
    }
}

void update(int nod, int st, int dr, int a, int b, int val){
    /// v[a..b] += val
    if(a <= st && dr <= b){
        aint[nod].lazy += val;
        change(nod, val);
    }else{
        propag(nod);
        int mid = ((st+dr)>>1);
        if(a <= mid){
            update(lc, st, mid, a, b, val);
        }
        if(b >= mid+1){
            update(rc, mid+1, dr, a, b, val);
        }
        merge(nod);
    }
}

void query(int nod, int st, int dr, int a, int b){
    /// maxim impar si minim par din [a..b]
    if(a <= st && dr <= b){
        maxi = max(maxi, aint[nod].maximp);
        mini = min(mini, aint[nod].minpar);
    }else{
        propag(nod);
        int mid = ((st+dr)>>1);
        if(a <= mid){
            query(lc, st, mid, a, b);
        }
        if(b >= mid+1){
            query(rc, mid+1, dr, a, b);
        }
        merge(nod);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    build(1, 1, n);
    cin >> q;
    while(q--){
        cin >> t >> x >> y;
        if(t == 0){
            cin >> v;
            update(1, 1, n, x, y, v);
        }else{
            mini = INF;
            maxi = -1;
            query(1, 1, n, x, y);
            cout << (mini == INF ? -1 : mini) << " " << maxi << "\n";
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31736 KB Output is correct
2 Correct 17 ms 31700 KB Output is correct
3 Correct 18 ms 31804 KB Output is correct
4 Correct 27 ms 31828 KB Output is correct
5 Correct 18 ms 31828 KB Output is correct
6 Correct 17 ms 31780 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 35700 KB Output is correct
2 Correct 239 ms 40064 KB Output is correct
3 Correct 242 ms 40116 KB Output is correct
4 Correct 257 ms 40084 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31736 KB Output is correct
2 Correct 17 ms 31700 KB Output is correct
3 Correct 18 ms 31804 KB Output is correct
4 Correct 27 ms 31828 KB Output is correct
5 Correct 18 ms 31828 KB Output is correct
6 Correct 17 ms 31780 KB Output is correct
7 Correct 114 ms 35700 KB Output is correct
8 Correct 239 ms 40064 KB Output is correct
9 Correct 242 ms 40116 KB Output is correct
10 Correct 257 ms 40084 KB Output is correct
11 Correct 170 ms 36192 KB Output is correct
12 Correct 306 ms 40508 KB Output is correct
13 Correct 274 ms 41292 KB Output is correct
14 Correct 307 ms 40604 KB Output is correct
15 Correct 266 ms 41776 KB Output is correct
16 Correct 99 ms 37964 KB Output is correct