Submission #744105

#	Time	Username	Problem	Language	Result	Execution time	Memory
744105		salmon	Weirdtree (RMI21_weirdtree)	C++14	21 / 100	466 ms	43676 KiB

weirdtree

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29