oj.uz

Submission #786578

# Submission time Handle Problem Language Result Execution time Memory
786578 2023-07-18T09:27:08 Z 이성호(#10028) Weirdtree (RMI21_weirdtree) C++17
13 / 100
 33 ms 24660 KB 
#include "weirdtree.h"
#include <vector>
#include <cmath>
using namespace std;
pair<int, int> mymax(pair<int, int> p1, pair<int, int> p2)
{
    return p1.first == p2.first ? (p1.second < p2.second ? p1 : p2) : (p1.first < p2.first ? p2 : p1);
}
struct FenWick
{
    vector<long long> tree;
    int n;
    void setup(int N)
    {
        n = N;
        tree.resize(n+1);
    }
    void upd(int i, int x)
    {
        for (; i <= n; i += i&-i) tree[i] += x;
    }
    long long query(int i)
    {
        long long ret = 0;
        for (; i; i -= i&-i) ret += tree[i];
        return ret;
    }
    long long calc(int l, int r)
    {
        return query(r) - query(l-1);
    }
}fenwick;

struct maxseg
{
    vector<pair<int, int>> tree;
    int n;
    int sz;
    void setup(int N)
    {
        n = N;
        int sz = 1 << ((int)ceil(log2(N+1))+1);
        tree.resize(sz);
    }
    pair<int, int> init(int s, int e, int node, int* h)
    {
        if (s == e) return tree[node] = make_pair(h[s], s);
        return tree[node] = mymax(init(s, (s+e)/2, 2*node, h), init((s+e)/2+1, e, 2*node+1, h));
    }
    void add(int id, int x)
    {
        upd(1, n, 1, id, x);
    }
    void upd(int s, int e, int node, int id, int x)
    {
        if (e < id || id < s) return;
        if (s == e) {
            tree[node].first += x;
            return;
        }
        upd(s, (s+e)/2, 2*node, id, x);
        upd((s+e)/2+1, e, 2*node+1, id, x);
        tree[node] = mymax(tree[2*node], tree[2*node+1]);
    }
    pair<int, int> calc(int l, int r)
    {
        return query(1, n, 1, l, r);
    }
    pair<int, int> query(int s, int e, int node, int l, int r)
    {
        if (e < l || r < s) return make_pair(-1, 0);
        if (l <= s && e <= r) return tree[node];
        return mymax(query(s, (s+e)/2, 2*node, l, r), query((s+e)/2+1, e, 2*node+1, l, r));
    }
}maxseg;

int arr[80005];

void initialise(int N, int Q, int h[]) {
	fenwick.setup(N); maxseg.setup(N);
	for (int i = 1; i <= N; i++) fenwick.upd(i, h[i]), arr[i] = h[i];
	maxseg.init(1, N, 1, h);
}
void cut(int l, int r, int k) {
    pair<int, int> tmp = maxseg.calc(l, r);
    if (tmp.first == 0) return;
    maxseg.add(tmp.second, -1);
    fenwick.upd(tmp.second, -1);
    arr[tmp.second]--;
}
void magic(int i, int x) {
	int p = arr[i]; arr[i] = x;
	maxseg.add(i, x-p);
	fenwick.upd(i, x-p);
}
long long int inspect(int l, int r) {
	return fenwick.calc(l, r);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 33 ms 4112 KB Output is correct
4 Correct 32 ms 4424 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 24660 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 33 ms 4112 KB Output is correct
4 Correct 32 ms 4424 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 33 ms 4112 KB Output is correct
4 Correct 32 ms 4424 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -