Submission #1318405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318405		ghammazhassan	Simple (info1cup19_simple)	C++20	30 / 100	266 ms	25976 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 int long long
#define endl "\n"
#define fi first
#define se second
const int M=1e9+7;
const int inf = 1e15;
const int LOG=17;
const int N=2e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
struct node
{
    int mno=inf,mne=inf;
    int mxo=-inf,mxe=-inf;
};
node join(node x,node y){
    node r;
    r.mxo=max(x.mxo,y.mxo);
    r.mxe=max(x.mxe,y.mxe);
    r.mno=min(x.mno,y.mno);
    r.mne=min(x.mne,y.mne);
    return r;
}
node seg[4*N];
int lz[4*N];
int a[N];
void build(int s=0,int e=n,int v=1){
    if (e-s==1){
        if (a[s]%2){
            seg[v].mno=seg[v].mxo=a[s];
        }
        else{
            seg[v].mne=seg[v].mxe=a[s];
        }
        return;
    }
    int li=2*v;
    int ri=2*v+1;
    int m=(s+e)/2;
    build(s,m,li);
    build(m,e,ri);
    seg[v]=join(seg[li],seg[ri]);
}
void update(int l,int r,int y,int s=0,int e=n,int v=1){
    int x=lz[v];
    lz[v]=0;
    if (e-s!=1){
        lz[2*v]+=x;
        lz[2*v+1]+=x;
    }
    seg[v].mno+=x;
    seg[v].mne+=x;
    seg[v].mxo+=x;
    seg[v].mxe+=x;
    if (r<=s or l>=e)return;
    if (l<=s and e<=r){
        int x=y+lz[v];
        lz[v]=0;
        if (e-s!=1){
            lz[2*v]+=x;
            lz[2*v+1]+=x;
        }
        seg[v].mno+=x;
        seg[v].mne+=x;
        seg[v].mxo+=x;
        seg[v].mxe+=x;
        if (x%2){
            swap(seg[v].mxo,seg[v].mxe);
            swap(seg[v].mno,seg[v].mne);
        }
        return;
    }
    int li=2*v;
    int ri=2*v+1;
    int m=(s+e)/2;
    update(l,r,y,s,m,li);
    update(l,r,y,m,e,ri);
    seg[v]=join(seg[li],seg[ri]);
}
node query(int l,int r,int s=0,int e=n,int v=1){
    int x=lz[v];
    lz[v]=0;
    if (e-s!=1){
        lz[2*v]+=x;
        lz[2*v+1]+=x;
    }
    seg[v].mno+=x;
    seg[v].mne+=x;
    seg[v].mxo+=x;
    seg[v].mxe+=x;
    if (x%2){
        swap(seg[v].mxo,seg[v].mxe);
        swap(seg[v].mno,seg[v].mne);
    }
    if (r<=s or l>=e)return node();
    if (l<=s and e<=r)return seg[v];
    int li=2*v;
    int ri=2*v+1;
    int m=(s+e)/2;
    node p=join(query(l,r,s,m,li),query(l,r,m,e,ri));
    seg[v]=join(seg[li],seg[ri]);
    return p;
}
void solve(){
    cin >> n;
    for (int i=0;i<n;i++){
        cin >> a[i];
    }
    build();
    cin >> q;
    for (int i=0;i<q;i++){
        cin >> x;
        if (x==0){
            cin >> l >> r >> x;
            l--;
            update(l,r,x);
        }
        else{
            cin >> l >> r;
            l--;
            node p=query(l,r);
            if (abs(p.mne)<5e14){
                cout << p.mne << " ";
            }
            else{
                cout << -1 << " ";
            }
            if (abs(p.mxo)<5e14){
                cout << p.mxo << endl;
            }
            else{
                cout << -1 << endl;
            }
        }
    }
}
signed main()    
{   
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r" ,stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed << setprecision(9);
    srand(time(0));
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
        solve();
        q++;
    }
}

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