#include <iostream>
#include <algorithm>
/*
we have something which stores how many elements we have at the back
*/
#define MAXN 500005
#define int long long
#define printf
struct query_t
{
int t, l, r;
};
int a[MAXN];
int occ[MAXN];
query_t queries[MAXN];
int occn = 0;
int occe = 0;
int n, q;
int pref[MAXN];
signed main1()
{
for (int i = 1; i <= n; ++i)
{
pref[i] = pref[i-1] + a[i];
}
for (int qp = 1; qp <= q; ++qp)
{
int t = queries[qp].t;
if (t == 1)
{
for (int j = 1; j <= n-1; ++j)
{
if (a[j] > a[j+1]) std::swap(a[j], a[j+1]);
pref[j] = pref[j-1] + a[j];
}
}
else
{
int l = queries[qp].l, r = queries[qp].r;
std::cout << pref[r] - pref[l-1] << "\n";
}
}
return 0;
}
signed main3()
{
int amount = 0;
for (int i = n; i >= 1 && a[i] == 2; --i) ++amount;
printf("amount: %i\n", amount);
for (int i = 1; i <= n-amount; ++i)
{
if (a[i] == 2)
{
occ[++occn] = i;
printf("occ[%i] = %i\n", occn, occ[occn]);
}
}
occ[++occn] = n-amount+1;
printf("occ[%i] = %i\n", occn, occ[occn]);
for (int qp = 1; qp <= q; ++qp)
{
// printf("%i, %i\n", qp, q);
int t = queries[qp].t;
if (t == 1)
{
if (occe >= occn-1) continue;
++occe;
}
else
{
int l = queries[qp].l, r = queries[qp].r;
int twos = 0;
if (occe < occn-1)
{
// the first index k such that data[k] - occe >= l <=> data[k] >= l + occe
// the last index k such that data[k] - occe <= r <=> data[k] <= r + occe
auto up = std::lower_bound(occ+occe+1, occ+occn, l + occe);
auto down = std::upper_bound(occ+occe+1, occ+occn, r + occe);
int hm = down - up;
twos += hm;
printf("bounds result: %i\n", hm);
}
int count_to = n - amount - occe + 1;
twos += std::min(r - l + 1, std::max((int)0, r - count_to + 1));
printf("count to: %i; twos=%i\n", count_to, twos);
std::cout << r - l + 1 + twos << "\n";
}
}
return 0;
}
int pmin[MAXN];
int q1cnt;
signed main2()
{
pmin[0] = (int)(1e10);
for (int i = 1; i <= n; ++i)
{
pmin[i] = std::min(pmin[i-1], a[i]);
}
q1cnt = 1;
for (int qp = 1; qp <= q; ++q)
{
int t = queries[qp].t;
if (t == 1)
{
++q1cnt;
}
else
{
std::cout << pmin[std::min(q1cnt, n)] << "\n";
}
}
return 0;
}
signed main()
{
std::cin >> n;
int case_three = 1;
for (int i = 1; i <= n; ++i)
{
std::cin >> a[i];
case_three = case_three && (a[i] == 1 || a[i] == 2);
}
std::cin >> q;
int q1c = 0;
int case_two = 1;
int case_four = 1;
for (int i = 1; i <= q; ++i)
{
std::cin >> queries[i].t;
if (queries[i].t == 2)
{
std::cin >> queries[i].l >> queries[i].r;
case_two = case_two && (queries[i].l == 1 && queries[i].r == 1);
case_four = case_four && (queries[i].l == queries[i].r);
}
else ++q1c;
}
int case_one = q1c <= 10;
if (case_three)
{
return main3();
}
else if (case_two)
{
return main2();
}
else if (case_one)
{
return main1();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |