oj.uz

Submission #1075850

# Submission time Handle Problem Language Result Execution time Memory
1075850 2024-08-26T09:31:01 Z horiaboeriu Simple (info1cup19_simple) C++17
100 / 100
 273 ms 40028 KB 
#include <stdio.h>
#include <stdlib.h>
#define MAX 200000
#define INFINIT 1000000000000000000
long long a[4 * MAX + 1], a1[4 * MAX + 1], b[4 * MAX + 1], b1[4 * MAX + 1], v[4 * MAX + 1];
char flag[4 * MAX + 1];
long long min, max;
//in a este min par
//in a1 este min impar
//in b este max par
//in b1 este max impar
//pun INFINIT sau -INFINIT daca nu exista par sau impar in acel interval
long long minim(long long x, long long y)  {
    return x < y ? x : y;
}
long long maxim(long long x, long long y) {
    return x > y ? x : y;
}
void calcul(int nod) {
    a[nod] = minim(a[2 * nod], a[2 * nod + 1]);
    a1[nod] = minim(a1[2 * nod], a1[2 * nod + 1]);

    b[nod] = maxim(b[2 * nod], b[2 * nod + 1]);
    b1[nod] = maxim(b1[2 * nod], b1[2 * nod + 1]);
}
void build(int nod, int st, int dr) {
    int mid, x;
    if (st == dr) {
        scanf("%d", &x);
        if (x % 2 == 0) {
            a[nod] = b[nod] = x;
            a1[nod] = INFINIT;
            b1[nod] = -INFINIT;
        } else {
            a1[nod] = b1[nod] = x;
            a[nod] = INFINIT;
            b[nod] = -INFINIT;
        }
    } else {
        mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
        calcul(nod);
    }
}
void prop(int nod, long long val) {
    long long aux;
    //fac acelasi lucru pentru a si b
    //adun val la ambele din a si voi actualiza minimul par si impar
    if (a[nod] == INFINIT) {
        if (val % 2 == 0) {
            a1[nod] += val;
        } else {
            a[nod] = a1[nod] + val;
            a1[nod] = INFINIT;
        }
    } else if (a1[nod] == INFINIT) {
        if (val % 2 == 0) {
            a[nod] += val;
        } else {
            a1[nod] = a[nod] + val;
            a[nod] = INFINIT;
        }
    } else {
        if (val % 2 == 0) {
            a[nod] += val;
            a1[nod] += val;
        } else {
            aux = a[nod];
            a[nod] = a1[nod] + val;
            a1[nod] = aux + val;
        }
    }

    if (b[nod] == -INFINIT) {
        if (val % 2 == 0) {
            b1[nod] += val;
        } else {
            b[nod] = b1[nod] + val;
            b1[nod] = -INFINIT;
        }
    } else if (b1[nod] == -INFINIT) {
        if (val % 2 == 0) {
            b[nod] += val;
        } else {
            b1[nod] = b[nod] + val;
            b[nod] = -INFINIT;
        }
    } else {
        if (val % 2 == 0) {
            b[nod] += val;
            b1[nod] += val;
        } else {
            aux = b[nod];
            b[nod] = b1[nod] + val;
            b1[nod] = aux + val;
        }
    }
}
void query(int nod, int st, int dr, int x, int y) {
    int mid;
    if (x <= st && y >= dr) {
        min = minim(min, a[nod]);
        max = maxim(max, b1[nod]);
    } else {
        mid = (st + dr) / 2;
        if (flag[nod] == 1) {//propag in jos cat am de adunat
            prop(2 * nod, v[nod]);
            prop(2 * nod + 1, v[nod]);

            flag[2 * nod] = flag[2 * nod + 1] = 1;
            v[2 * nod] += v[nod];
            v[2 * nod + 1] += v[nod];
            flag[nod] = v[nod] = 0;
        }
        if (x <= mid) {
            query(2 * nod, st, mid, x, y);
        }
        if (y > mid) {
            query(2 * nod + 1, mid + 1, dr, x, y);
        }
        calcul(nod);
    }
}
void update(int nod, int st, int dr, int x, int y, int val) {
    int mid;
    if (x <= st && y >= dr) {
        prop(nod, (long long)val);
        flag[nod] = 1;
        v[nod] += val;
    } else {
        mid = (st + dr) / 2;
        if (flag[nod] == 1) {//propag in jos cat am de adunat
            prop(2 * nod, v[nod]);
            prop(2 * nod + 1, v[nod]);

            flag[2 * nod] = flag[2 * nod + 1] = 1;
            v[2 * nod] += v[nod];
            v[2 * nod + 1] += v[nod];
            flag[nod] = v[nod] = 0;
        }
        if (x <= mid) {
            update(2 * nod, st, mid, x, y, val);
        }
        if (y > mid) {
            update(2 * nod + 1, mid + 1, dr, x, y, val);
        }
        calcul(nod);
    }
}
int main()
{
    int n, q, i, x, y, nr, cer;
    scanf("%d", &n);
    build(1, 1, n);
    scanf("%d", &q);
    for (i = 0; i < q; i++) {
        scanf("%d", &cer);
        if (cer == 0) {
            scanf("%d%d%d", &x, &y, &nr);
            update(1, 1, n, x, y, nr);
        } else {
            scanf("%d%d", &x, &y);
            min = INFINIT;
            max = -INFINIT;
            query(1, 1, n, x, y);
            if (min == INFINIT) {
                min = -1;
            }
            if (max == -INFINIT) {
                max = -1;
            }
            printf("%lld %lld\n", min, max);
        }
    }
    return 0;
}

Compilation message

subway.cpp: In function 'void build(int, int, int)':
subway.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
subway.cpp: In function 'int main()':
subway.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
subway.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
subway.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         scanf("%d", &cer);
      |         ~~~~~^~~~~~~~~~~~
subway.cpp:160:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |             scanf("%d%d%d", &x, &y, &nr);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
subway.cpp:163:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |             scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 5 ms 10844 KB Output is correct
4 Correct 5 ms 10844 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 20944 KB Output is correct
2 Correct 167 ms 33468 KB Output is correct
3 Correct 193 ms 33356 KB Output is correct
4 Correct 205 ms 27176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 5 ms 10844 KB Output is correct
4 Correct 5 ms 10844 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 80 ms 20944 KB Output is correct
8 Correct 167 ms 33468 KB Output is correct
9 Correct 193 ms 33356 KB Output is correct
10 Correct 205 ms 27176 KB Output is correct
11 Correct 108 ms 19792 KB Output is correct
12 Correct 265 ms 38444 KB Output is correct
13 Correct 244 ms 39696 KB Output is correct
14 Correct 273 ms 38888 KB Output is correct
15 Correct 223 ms 40028 KB Output is correct
16 Correct 65 ms 31572 KB Output is correct