Submission #645340

#	Time	Username	Problem	Language	Result	Execution time	Memory
645340		notme	Simple (info1cup19_simple)	C++14	100 / 100	353 ms	32692 KiB

subway

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 2e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, a[MAXN];
void read_array()
{
    cin >> n;
    for (long long i = 1; i <= n; ++ i)
    {
        cin >> a[i];
    }
}

struct node
{
    long long mineven, maxeven, minodd, maxodd;
    node(){};
    node(long long _mineven, long long _maxeven, long long _minodd, long long _maxodd)
    {
        mineven = _mineven;
        maxeven = _maxeven;
        minodd = _minodd;
        maxodd = _maxodd;
    }
};

node t[4 * MAXN];
long long lazy[4 * MAXN];
void make_tree(long long i, long long l, long long r)
{
    if(l == r)
    {
        if(a[l] & 1)
        {
            t[i].maxodd = a[l];
            t[i].minodd = a[l];
            t[i].maxeven = -1;
            t[i].mineven = 1e17;
        }
        else
        {
            t[i].maxeven = a[l];
            t[i].mineven = a[l];
            t[i].maxodd = -1;
            t[i].minodd = 1e17;
        }
        return;
    }
    long long mid = (l + r)/2;
    make_tree(2*i, l, mid);
    make_tree(2*i+1, mid+1, r);
    t[i].maxodd = max(t[2*i].maxodd, t[2*i+1].maxodd);
    t[i].minodd = min(t[2*i].minodd, t[2*i+1].minodd);
    t[i].maxeven = max(t[2*i].maxeven, t[2*i+1].maxeven);
    t[i].mineven = min(t[2*i].mineven, t[2*i+1].mineven);
}

void push_lazy(long long i, long long l, long long r)
{
    if(t[i].maxodd != -1)t[i].maxodd = t[i].maxodd + lazy[i];
    if(t[i].minodd != 1e17)t[i].minodd = t[i].minodd + lazy[i];
    if(t[i].maxeven != -1)t[i].maxeven = t[i].maxeven + lazy[i];
    if(t[i].mineven != 1e17)t[i].mineven = t[i].mineven + lazy[i];
    if(lazy[i] & 1)
    {

        swap(t[i].maxodd, t[i].maxeven);
        swap(t[i].minodd, t[i].mineven);

    }
    if(l != r)
    {
        lazy[2*i] += lazy[i];
        lazy[2*i+1] += lazy[i];
    }
    lazy[i] = 0;
}
long long ql, qr;
pair < long long/**minimum even*/, long long/**maxodd*/> query(long long i, long long l, long long r)
{
   // cout << i << " " << l << " " << r << endl;
   push_lazy(i, l, r);
    if(qr < l || ql > r)return make_pair(1e17, -1);
    if(ql <= l && r <= qr)
    {
        return make_pair(t[i].mineven, t[i].maxodd);
    }
    long long mid = (l + r)/2;
    pair < long long , long long > first_half = query(2*i, l, mid);
    pair < long long, long long > second_half = query(2*i+1, mid+1, r);
    pair < long long, long long > ans = make_pair(min(first_half.first, second_half.first), max(first_half.second, second_half.second));
    return ans;
}
long long val;
void update(long long i, long long l, long long r)
{
    push_lazy(i, l, r);
    if(qr < l || ql > r)return;
    if(ql <= l && r <= qr)
    {
        lazy[i] += val;
        push_lazy(i, l, r);
        return;
    }
    int mid = (l + r)/2;
    update(2*i, l, mid);
    update(2*i+1, mid+1, r);
    t[i].maxodd = max(t[2*i].maxodd, t[2*i+1].maxodd);
    t[i].minodd = min(t[2*i].minodd, t[2*i+1].minodd);
    t[i].maxeven = max(t[2*i].maxeven, t[2*i+1].maxeven);
    t[i].mineven = min(t[2*i].mineven, t[2*i+1].mineven);
}
int main()
{
   speed();

    read_array();
    make_tree(1, 1, n);
    long long q;
    cin >> q;
    long long type;
    while(q --)
    {
        cin >> type;
        if(type == 1)
        {
            cin >> ql >> qr;
            pair < long long, long long > qq = query(1, 1, n);

            if(qq.first == 1e17)cout << -1 << " ";
            else cout << qq.first << " ";
            if(qq.second == -1)cout << -1 << endl;
            else cout << qq.second << endl;
            //cout << .first << " " << query(1, 1, n).second << endl;
        }
        else
        {
            cin >> ql >> qr >> val;
            update(1, 1, n);
        }
    }
    return 0;
}

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