oj.uz

Submission #645340

# Submission time Handle Problem Language Result Execution time Memory
645340 2022-09-26T20:01:36 Z notme Simple (info1cup19_simple) C++14
100 / 100
 353 ms 32692 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 6 ms 1108 KB Output is correct
4 Correct 6 ms 1244 KB Output is correct
5 Correct 6 ms 1236 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 13012 KB Output is correct
2 Correct 299 ms 25820 KB Output is correct
3 Correct 293 ms 25960 KB Output is correct
4 Correct 287 ms 25820 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 6 ms 1108 KB Output is correct
4 Correct 6 ms 1244 KB Output is correct
5 Correct 6 ms 1236 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct
7 Correct 131 ms 13012 KB Output is correct
8 Correct 299 ms 25820 KB Output is correct
9 Correct 293 ms 25960 KB Output is correct
10 Correct 287 ms 25820 KB Output is correct
11 Correct 154 ms 16100 KB Output is correct
12 Correct 351 ms 31300 KB Output is correct
13 Correct 337 ms 32156 KB Output is correct
14 Correct 353 ms 31380 KB Output is correct
15 Correct 312 ms 32692 KB Output is correct
16 Correct 89 ms 24756 KB Output is correct