oj.uz

Submission #645959

# Submission time Handle Problem Language Result Execution time Memory
645959 2022-09-28T10:58:07 Z TimDee Weirdtree (RMI21_weirdtree) C++17
61 / 100
 271 ms 27488 KB 
#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;
//#define int 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;
		n=a.size();
		a.push_back(-1e9);
		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(ll i, ll 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);
	}

	ll 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;
		ll L=query(2*i+1,l,mid,lx,rx);
		ll R=query(2*i+2,mid,r,lx,rx);
		return merge(L,R);
	}

	ll 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);
ll sum=0;

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

ll f(int x,int L, int R) {
	ll r=0;
	for(int i=L-1; i<R; ++i) if (a[i]>x) r+=a[i]-x;
	return r;
}

void cut(int l, int r, int k) {
	if (l==1 && r==n && n>1000) {
		sum-=k;
		return;
	}
	//cout<<"cut "<<l<<' '<<r<<' '<<k<<'\n';
	if (k==1) {
		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]);
		}
	} else {

		int L=l, R=r;
		ll S=st.query(L-1,R);
		if (S<=k) {
			for (int i=L-1; i<R; ++i) a[i]=0;
			for (int i=L-1; i<R; ++i) st.set(i,0);
			for (int i=L-1; i<R; ++i) rmq.set(i,0);
			return;
		}
		int l=1, r=1e9;
		while (l<r) {
			int mid=(l+r)>>1;
			ll x=f(mid,L,R);
			if (x>=k) l=mid+1;
			else r=mid;
		}
		ll s=0;
		for (int i=L-1; i<R; ++i) {
			if (a[i]>r) {
				s+=a[i]-r;
				a[i]=r;
				st.set(i,r);
				rmq.set(i,r);
			}
		}
		k-=s;
		//cout<<r<<' '<<s<<' '<<k<<'\n';
		//for (auto x:a) cout<<x<<' '; cout<<'\n';
		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]);
		}
		//for (auto x:a) cout<<x<<' '; cout<<'\n';
	}
}

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

ll inspect(int l, int r) {
	if (l==1 && r==n && n>1000) {
		return sum;
	}
	ll ans=st.query(l-1,r);
	return ans;
}

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 51 ms 7304 KB Output is correct
4 Correct 49 ms 7244 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 340 KB Output is correct
2 Correct 26 ms 452 KB Output is correct
3 Correct 271 ms 27368 KB Output is correct
4 Correct 253 ms 27488 KB Output is correct
5 Correct 265 ms 27216 KB Output is correct
6 Correct 262 ms 27152 KB Output is correct
7 Correct 10 ms 7860 KB Output is correct
8 Correct 10 ms 8632 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7860 KB Output is correct
2 Correct 10 ms 8632 KB Output is correct
3 Incorrect 113 ms 26312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
21.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 51 ms 7304 KB Output is correct
4 Correct 49 ms 7244 KB Output is correct
5 Correct 13 ms 340 KB Output is correct
6 Correct 26 ms 452 KB Output is correct
7 Correct 10 ms 7860 KB Output is correct
8 Correct 10 ms 8632 KB Output is correct
9 Correct 47 ms 9072 KB Output is correct
10 Correct 52 ms 9108 KB Output is correct
11 Correct 47 ms 8940 KB Output is correct
12 Correct 49 ms 9216 KB Output is correct
13 Correct 47 ms 9172 KB Output is correct

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 51 ms 7304 KB Output is correct
4 Correct 49 ms 7244 KB Output is correct
5 Correct 13 ms 340 KB Output is correct
6 Correct 26 ms 452 KB Output is correct
7 Correct 271 ms 27368 KB Output is correct
8 Correct 253 ms 27488 KB Output is correct
9 Correct 265 ms 27216 KB Output is correct
10 Correct 262 ms 27152 KB Output is correct
11 Incorrect 113 ms 26312 KB Output isn't correct
12 Halted 0 ms 0 KB -