제출 #1318412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318412		hssaan_arif	Simple (info1cup19_simple)	C++20	100 / 100	206 ms	27336 KiB

subway

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second

const int N = 2e5 + 5, M = 1e9 + 7, LG = 20;

struct node
{
    int em = 1e15 , ex = -1e15 , om = 1e15 , ox = -1e15 , lz = 0;
};

node seg[4*N];

int n , A[N] , l , r , val , t , q;

node join(node a , node b){
    node res;

    res.em = min(a.em , b.em);
    res.ex = max(a.ex , b.ex);
    res.om = min(a.om , b.om);
    res.ox = max(a.ox , b.ox);

    return res;
}

void push(int n){
    seg[2*n].em += seg[n].lz;
    seg[2*n].ex += seg[n].lz;
    seg[2*n].om += seg[n].lz;
    seg[2*n].ox += seg[n].lz;
    seg[2*n].lz += seg[n].lz;

    seg[2*n+1].em += seg[n].lz;
    seg[2*n+1].ex += seg[n].lz;
    seg[2*n+1].om += seg[n].lz;
    seg[2*n+1].ox += seg[n].lz;
    seg[2*n+1].lz += seg[n].lz;

    if (seg[n].lz & 1){
        swap(seg[2*n].em , seg[2*n].om);
        swap(seg[2*n].ex , seg[2*n].ox);
        swap(seg[2*n+1].em , seg[2*n+1].om);
        swap(seg[2*n+1].ex , seg[2*n+1].ox);
    }

    seg[n].lz = 0;
}

void build(int n , int s , int e){
    if (s+1 == e){
        if (A[s] & 1){
            seg[n].om = A[s];
            seg[n].ox = A[s];
        }else{
            seg[n].em = A[s];
            seg[n].ex = A[s];
        }
    } else{
        int mid = (s+e)/2;

        build(2*n , s , mid);
        build(2*n+1 , mid , e);

        seg[n] = join(seg[2*n] , seg[2*n+1]);
    }
}

void upd(int n , int s , int e , int l , int r , int val){
    if (e <= l || r <= s){
        return;
    }

    if (l <= s && e <= r){
        seg[n].em += val;
        seg[n].ex += val;
        seg[n].om += val;
        seg[n].ox += val;
        seg[n].lz += val;

        if (val & 1){
            swap(seg[n].em , seg[n].om);
            swap(seg[n].ex , seg[n].ox);
        }
        
        return;
    }

    int mid = (s+e)/2;
    push(n);

    upd(2*n , s , mid , l , r , val);
    upd(2*n+1 , mid , e , l , r , val);

    seg[n] = join(seg[2*n] , seg[2*n+1]);
}

node ans(int n , int s , int e  , int l , int r){
    if (e <= l || r <= s){
        node res;
        return res;
    }

    if (l <= s && e <= r){
        return seg[n];
    }

    int mid = (s+e)/2;
    push(n);

    return join(ans(2*n , s , mid , l , r) , ans(2*n+1 , mid , e , l , r));
}

void solve(){
    cin >> n;

    for (int i=1 ; i<=n ; i++){
        cin >> A[i];
    }

    build(1 , 1 , n+1);

    cin >> q;

    while(q--){
        cin >> t >> l >> r;

        if (t==0){
            cin >> val;
            upd(1 , 1 , n+1 , l , r+1 , val);
        }else{
            node res = ans(1 , 1 , n+1 , l , r+1);

            if (res.em < 1e15){
                cout << res.em << ' ';
            }else{
                cout << -1 << ' ';
            }

            if (res.ox > 0){
                cout << res.ox << ' ';
            }else{
                cout << -1 << ' ';
            }

            cout << endl;
        }
    }
}

signed main(){
    // freopen("" , "r" , stdin);
    // freopen("" , "w" , stdout);
    // cout << setprecision(30);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40