Submission #1075850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075850		horiaboeriu	Simple (info1cup19_simple)	C++17	100 / 100	273 ms	40028 KiB

subway

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40