oj.uz

Submission #598636

# Submission time Handle Problem Language Result Execution time Memory
598636 2022-07-18T15:38:40 Z CaroLinda Weirdtree (RMI21_weirdtree) C++14
13 / 100
 2000 ms 6104 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>

//solving for k == 1

#define ll long long

const int MAXN = 8e4+10;

using namespace std;

int N, Q;
int mx[MAXN*4];
ll soma[MAXN*4];

int m(int l, int r){
	return (l+r)>>1;
}

void updPoint(int pos, int l, int r, int id, int val){
	if(l == r){
		mx[pos] = val;
		soma[pos] = val;
		return;
	}

	if(id <= m(l,r))
		updPoint(pos<<1, l, m(l,r), id, val);
	else updPoint(pos<<1|1, m(l,r)+1, r, id, val);

	soma[pos] = soma[pos<<1]+soma[pos<<1|1];
	mx[pos] = max(mx[pos<<1],mx[pos<<1|1]);
}

ll qry(int pos, int l, int r, int beg, int en){
	if( l > en || r < beg)
		return 0LL;

	if(l >= beg && r <= en)
		return soma[pos];

	ll al = qry(pos<<1 , l , m(l,r), beg, en);
	ll ar = qry(pos<<1|1,m(l,r)+1, r, beg, en);

	return al+ar;
}

vector<tuple<int,int,int> > q;

void findVector(int pos, int l, int r, int beg, int en){
	if(l > en || r < beg)
		return ;

	if(l >= beg && r <= en)
		return (void)(q.push_back(make_tuple(pos,l,r)));

	findVector(pos<<1 , l, m(l,r), beg, en);
	findVector(pos<<1|1, m(l,r)+1, r, beg, en);
}

void updateInside(int pos, int l, int r){
	soma[pos]--;
	if(l == r){
		mx[pos]--;
		return;
	}

	if(mx[pos] == mx[pos<<1])
		updateInside(pos<<1 , l ,m(l,r));
	else updateInside(pos<<1|1 , m(l,r)+1, r);

	mx[pos] = max(mx[pos<<1], mx[pos<<1|1]);
}

void updateBig(int pos, int l, int r, int beg, int en){
	if(l == beg && r == en)
		return;

	if(en <= m(l,r))
		updateBig(pos<<1 , l , m(l,r), beg, en );
	else updateBig(pos<<1|1,m(l,r)+1, r, beg, en);

	soma[pos] = soma[pos<<1]+soma[pos<<1|1];
	mx[pos] = max(mx[pos<<1], mx[pos<<1|1]);
}

void callUpdateMax(int beg, int en){
	q.clear();
	findVector(1,1,N,beg,en);

	int curMax = 0, pos = -1, l, r;

	for(auto &e: q){
		if(mx[get<0>(e)] > curMax){
			curMax = mx[get<0>(e)];
			pos = get<0>(e);
			l = get<1>(e);
			r = get<2>(e);
		}
	}

	//there is nothing to do
	if(pos == -1)
		return;

	//go to max
	updateInside(pos, l,r);
	updateBig(1,1,N, l, r);
}


void initialise(int n, int q, int h[]) {
	N = n;
	Q = q;

	for(int i = 1; i <= N; i++)
		updPoint(1,1,N, i, h[i]);
}
void cut(int l, int r, int k) {
	while(k--){
		callUpdateMax(l,r);
	}
}
void magic(int i, int x) {
	updPoint(1,1,N, i, x);
}
long long int inspect(int l, int r) {
	return qry(1,1,N, 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 43 ms 6104 KB Output is correct
4 Correct 45 ms 6076 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 340 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 2071 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 5708 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 43 ms 6104 KB Output is correct
4 Correct 45 ms 6076 KB Output is correct
5 Execution timed out 2071 ms 340 KB Time limit exceeded
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 43 ms 6104 KB Output is correct
4 Correct 45 ms 6076 KB Output is correct
5 Execution timed out 2071 ms 340 KB Time limit exceeded
6 Halted 0 ms 0 KB -