Submission #645930

#	Time	Username	Problem	Language	Result	Execution time	Memory
645930		TimDee	Weirdtree (RMI21_weirdtree)	C++17	Compilation error	0 ms	0 KiB

weirdtree

#include <iostream>

//#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
using ll = long long;

struct RMQ {

	vector<ll>t,a;
	int size=1, n;

	int merge(int i, int j) {
		if (a[i]>=a[j]) return i;
		else return j;
	}

	void update(int i, int l, int r, int p) {
		if (r-l==1) return;
		if (r<=p || l>p) return;
		int mid=(r+l)>>1;
		update(2*i+1,l,mid,p);
		update(2*i+2,mid,r,p);
		t[i]=merge(t[2*i+1],t[2*i+2]);
	}

	void update(int i, int l, int r) {
		if (r-l==1) return;
		int mid=(r+l)>>1;
		update(2*i+1,l,mid);
		update(2*i+2,mid,r);
		t[i]=merge(t[2*i+1],t[2*i+2]);
	}

	RMQ(vector<ll>&v) {
		a=v;
		a.push_back(-1e9);
		n=a.size();
		while (size<n) size<<=1;
		t.assign(2*size-1,n);
		forn(i,n) t[size-1+i]=i;
		update(0,0,size);
	}

	int query(int i, int l, int r, int lx, int rx) {
		if (l>=rx || r<=lx) return n;
		if (l>=lx && r<=rx) return t[i];
		int mid=(l+r)>>1;
		int L=query(2*i+1,l,mid,lx,rx);
		int R=query(2*i+2,mid,r,lx,rx);
		return merge(L,R);
	}

	int query(int l, int r) {
		return query(0,0,size,l,r);
	}

	void set(int i, int x) {
		a[i]=x;
		update(0,0,size,i);
	}

};

struct aint {

	vector<ll>t,a;
	int size=1, n;

	ll merge(int i, int j) {
		return i+j;
	}

	void update(int i, int l, int r, int p) {
		if (r-l==1) return;
		if (r<=p || l>p) return;
		int mid=(r+l)>>1;
		update(2*i+1,l,mid,p);
		update(2*i+2,mid,r,p);
		t[i]=merge(t[2*i+1],t[2*i+2]);
	}

	void update(int i, int l, int r) {
		if (r-l==1) return;
		int mid=(r+l)>>1;
		update(2*i+1,l,mid);
		update(2*i+2,mid,r);
		t[i]=merge(t[2*i+1],t[2*i+2]);
	}

	aint(vector<ll>&v) {
		a=v;
		n=a.size();
		while (size<n) size<<=1;
		t.assign(2*size-1,0);
		forn(i,n) t[size-1+i]=a[i];
		update(0,0,size);
	}

	int query(int i, int l, int r, int lx, int rx) {
		if (l>=rx || r<=lx) return 0;
		if (l>=lx && r<=rx) return t[i];
		int mid=(l+r)>>1;
		int L=query(2*i+1,l,mid,lx,rx);
		int R=query(2*i+2,mid,r,lx,rx);
		return merge(L,R);
	}

	int query(int l, int r) {
		return query(0,0,size,l,r);
	}

	void set(int i, int x) {
		t[size-1+i]=x;
		update(0,0,size,i);
	}

};

vector<ll> a;
int n;
aint st(a);
RMQ rmq(a);

initialise(int N, int Q, int*v) {
	n=N;
	forn(i,n) a.push_back(v[i+1]);
	st=aint(a);
	rmq=RMQ(a);
}

void cut(int l, int r, int k) {
	forn(q,k) {
		int i=rmq.query(l-1,r);
		if (!a[i]) break;
		a[i]--;
		rmq.set(i,a[i]);
		st.set(i,a[i]);
	}
}

void magic(int i, int x) {
	--i;
	a[i]=x;
	rmq.set(i,x);
	st.set(i,x);
}

ll inspect(int l, int r) {
	ll ans=st.query(l-1,r);
	return ans;
}

int main() {
    int N, Q;
    cin >> N >> Q;

    int h[N + 1];

    for (int i = 1; i <= N; ++i) cin >> h[i];

    initialise(N, Q, h);

    for (int i = 1; i <= Q; ++i) {
        int t;
        cin >> t;

        if (t == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            cut(l, r, k);
        } else if (t == 2) {
            int i, x;
            cin >> i >> x;
            magic(i, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << inspect(l, r) << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

weirdtree.cpp:126:1: error: ISO C++ forbids declaration of 'initialise' with no type [-fpermissive]
  126 | initialise(int N, int Q, int*v) {
      | ^~~~~~~~~~
weirdtree.cpp: In function 'int initialise(int, int, int*)':
weirdtree.cpp:131:1: warning: no return statement in function returning non-void [-Wreturn-type]
  131 | }
      | ^