oj.uz

Submission #597746

# Submission time Handle Problem Language Result Execution time Memory
597746 2022-07-16T19:03:28 Z ThegeekKnight16 Weirdtree (RMI21_weirdtree) C++17
5 / 100
 2000 ms 33312 KB 
#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)
{
    while (K > 0)
    {
        node atual = query(1, 1, N, L, R);
        //cerr << atual.Max << " " << atual.Max2 << '\n';
        if (atual.Max <= 0) return;
        int Maximo = atual.Max;
        int novoMaximo = max(Maximo - K, atual.Max2 - 1);
        novoMaximo = max(novoMaximo, 0);
        //cerr << Maximo << " " << novoMaximo << '\n';
        K -= (Maximo - novoMaximo);
        update(1, 1, N, atual.idMax, novoMaximo);
    }
}
 
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';
        }
    }
}*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28500 KB Output is correct
2 Correct 17 ms 28500 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28500 KB Output is correct
2 Correct 17 ms 28500 KB Output is correct
3 Correct 413 ms 30844 KB Output is correct
4 Incorrect 430 ms 31000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 28584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 28584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1012 ms 33312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28500 KB Output is correct
2 Correct 17 ms 28500 KB Output is correct
3 Correct 413 ms 30844 KB Output is correct
4 Incorrect 430 ms 31000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28500 KB Output is correct
2 Correct 17 ms 28500 KB Output is correct
3 Correct 413 ms 30844 KB Output is correct
4 Incorrect 430 ms 31000 KB Output isn't correct
5 Halted 0 ms 0 KB -