This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <weirdtree.h>
using namespace std;
struct node
{
int Max, Max2;
long long int Sum;
int idMax, idMax2;
node() {Max = 0; Max2 = 0; idMax = 0; idMax2 = 0; Sum = 0LL;}
node operator+(node outro)
{
vector<pair<int, int>> v;
v.push_back(make_pair(Max, idMax)); v.push_back(make_pair(Max2, idMax2));
v.push_back(make_pair(outro.Max, outro.idMax)); v.push_back(make_pair(outro.Max2, outro.idMax2));
sort(v.begin(), v.end());
node resp;
resp.Max = v[3].first; resp.idMax = v[3].second;
resp.Max2 = v[2].first; resp.idMax2 = v[2].second;
resp.Sum = Sum + outro.Sum;
/*cerr << Max << " " << Max2 << '\n';
cerr << " + " << '\n';
cerr << outro.Max << " " << outro.Max2 << '\n';
cerr << " = " << '\n';
cerr << resp.Max << " " << resp.Max2 << '\n';*/
return resp;
}
};
const int MAXN = 3e5 + 10;
node seg[4*MAXN];
node nulo;
int N;
node query(int pos, int ini, int fim, int p, int q)
{
if (q < ini || p > fim) return nulo;
if (p <= ini && fim <= q) return seg[pos];
int m = (ini + fim) / 2;
int e = 2*pos; int d = 2*pos + 1;
return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
}
void update(int pos, int ini, int fim, int id, int val)
{
if (id < ini || id > fim) return;
if (ini == fim)
{
seg[pos].Max = val;
seg[pos].Max2 = 0;
seg[pos].Sum = (long long int)val;
seg[pos].idMax = seg[pos].idMax2 = id;
//cerr << id << '\n';
//cerr << seg[id].Max << " " << seg[id].Max2 << '\n';
return;
}
int m = (ini + fim) / 2;
int e = 2*pos; int d = 2*pos + 1;
update(e, ini, m , id, val);
update(d, m+1, fim, id, val);
seg[pos] = (seg[e] + seg[d]);
}
void cut(int L, int R, int K)
{
node atual = query(1, 1, N, L, R);
//cerr << atual.Max << " " << atual.Max2 << '\n';
if (atual.Max <= 0) return;
//cerr << Maximo << " " << novoMaximo << '\n';
//K -= (Maximo - novoMaximo);
update(1, 1, N, atual.idMax, ((atual.Max) - 1));
}
long long int inspect(int L, int R)
{
node resp = query(1, 1, N, L, R);
return resp.Sum;
}
void magic(int id, int val)
{
update(1, 1, N, id, val);
}
void initialise(int n, int Q, int h[])
{
N = n;
for (int i = 1; i <= N; i++) update(1, 1, N, i, h[i]);
}
/*int main()
{
int n, Q;
cin >> n >> Q;
int altura[N+10];
for (int i = 1; i <= n; i++) cin >> altura[i];
initialise(n, Q, altura);
for (int q = 1; q <= Q; q++)
{
int type;
cin >> type;
if (type == 1)
{
int X, Y, val;
cin >> X >> Y >> val;
cut(X, Y, val);
}
else if (type == 2)
{
int id, val;
cin >> id >> val;
magic(id, val);
}
else
{
int X, Y;
cin >> X >> Y;
cout << inspect(X, Y) << '\n';
}
}
}*/
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |