oj.uz

Submission #744105

# Submission time Handle Problem Language Result Execution time Memory
744105 2023-05-18T08:11:08 Z salmon Weirdtree (RMI21_weirdtree) C++14
21 / 100
 466 ms 43676 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> lst;
priority_queue<int> pq;
int n,q;

struct node{

	node *l,*r;
	int s,e,m;
	long long int v;
	pair<int,int> small;

	node(int S,int E){
		s = S;
		e = E;
		m = (s + e)/2;

		if(s == e){
			v = lst[s];
			small = make_pair(lst[s],-s);
		}
		else{
			l = new node(s,m);
			r = new node(m + 1, e);

			small = max(l -> small, r -> small);
			v = l -> v + (long long int) r -> v;
		}
	}

	long long int query(int S, int E){
		if(S <= s && e <= E){
			return v;
		}

		long long int V = 0;

		if(S <= m){
			V += l -> query(S,E);
		}
		if(m < E){
			V += r -> query(S,E);
		}

		return V;
	}

	pair<int,int> rmin(int S, int E){
		if(S <= s && e <= E){
			return small;
		}

		pair<int,int> V = make_pair(-1,0);

		if(S <= m) V = max(V,l -> rmin(S,E));
		if(m < E) V = max(V,r -> rmin(S,E));

		return V;
	}

	void update(int i, int k){
		if(s == e){
			v = k;
			small = make_pair(k,-s);
			return;
		}


		if(i <= m) l -> update(i,k);
		else r -> update(i,k);

		small = max(l -> small, r -> small);
		v = l -> v + (long long int) r -> v;


	}
}*root;

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



	lst.push_back(0);
	for(int i = 1; i <= N; i++){
		lst.push_back(h[i]);
	}

	root = new node(1,N);
}

void cut(int l, int r, int k) {
    if(n <= 1000 && q <= 1000){

        while(!pq.empty()){
            pq.pop();
        }

        for(int i = l; i <= r; i++){
            pq.push(lst[i]);
        }

        pq.push(0);

        int num = 0;
        int v = 0;
        while(!pq.empty() && k >= (v - pq.top()) * (long long int)num ){
            k = k - (v - pq.top()) * num;
            num++;
            v = pq.top();
            pq.pop();
        }

        if(pq.empty()){
            for(int i = l; i <= r; i++){
                lst[i] = 0;
            }
            return;
        }

        int unnuse = k % num;
        int nam = k / num;
        v = v - nam;

        for(int i = l; i <= r; i++){
            if(lst[i] >= v){
                if(unnuse >= 1){
                    lst[i] = v - 1;
                    unnuse--;
                }
                else{
                    lst[i] = v;
                }
            }
        }

    }
    else{

        pair<int,int> ii = root -> rmin(l,r);

        if(ii.first == 0){
            return;
        }

        root -> update(-ii.second,ii.first - 1);
    }

    /*for(int i = 0; i < lst.size(); i++){
        printf("%d ",lst[i]);
    }
    printf("\n");*/
}
void magic(int i, int x) {
        if(n <= 1000 && q <= 1000){

	lst[i] = x;
        }
        else{
            root -> update(i,x);
        }
}
long long int inspect(int l, int r) {
    if(n > 1000 || q > 1000){
        return root -> query(l,r);
    }

	long long int V = 0;

	for(int i = l; i <= r; i++){
        V = V + lst[i];
	}

	return V;
}
/*
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> lst;



void initialise(int N, int Q, int h[]) {
	lst.push_back(0);
	for(int i = 1; i <= N; i++){
		lst.push_back(h[i]);
	}

	root = new node(1,N);
}

void cut(int l, int r, int k) {

}
void magic(int i, int x) {
	root -> update(i,x);
}
long long int inspect(int l, int r) {
	return root -> query(l,r);
}
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 468 KB Output is correct
2 Correct 8 ms 468 KB Output is correct
3 Correct 81 ms 10904 KB Output is correct
4 Correct 84 ms 10792 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 468 KB Output is correct
2 Correct 8 ms 488 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 468 KB Output is correct
2 Correct 8 ms 488 KB Output is correct
3 Correct 466 ms 41656 KB Output is correct
4 Correct 446 ms 43676 KB Output is correct
5 Correct 465 ms 41956 KB Output is correct
6 Correct 453 ms 41804 KB Output is correct
7 Incorrect 21 ms 11476 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 468 KB Output is correct
2 Correct 8 ms 468 KB Output is correct
3 Correct 81 ms 10904 KB Output is correct
4 Correct 84 ms 10792 KB Output is correct
5 Correct 11 ms 468 KB Output is correct
6 Correct 8 ms 488 KB Output is correct
7 Incorrect 21 ms 11476 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 468 KB Output is correct
2 Correct 8 ms 468 KB Output is correct
3 Correct 81 ms 10904 KB Output is correct
4 Correct 84 ms 10792 KB Output is correct
5 Correct 11 ms 468 KB Output is correct
6 Correct 8 ms 488 KB Output is correct
7 Correct 466 ms 41656 KB Output is correct
8 Correct 446 ms 43676 KB Output is correct
9 Correct 465 ms 41956 KB Output is correct
10 Correct 453 ms 41804 KB Output is correct
11 Incorrect 21 ms 11476 KB Output isn't correct
12 Halted 0 ms 0 KB -