oj.uz

Submission #599220

# Submission time Handle Problem Language Result Execution time Memory
599220 2022-07-19T11:44:45 Z CaroLinda Weirdtree (RMI21_weirdtree) C++14
27 / 100
 576 ms 40296 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>

#define ll long long

const int inf = 1e9+10;
const int MAXN = 3e5+10;

using namespace std;


// ------ DECLARATIONS ------
int N, Q;
struct Node{
	int mx, fmx, secmx;
	ll s;
} t[MAXN << 2];
int tag[MAXN << 2];
bool isLeaf[MAXN << 2];
// --------------------------

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

Node operator + (Node A, Node B){
	if(A.mx < B.mx)
		swap(A,B);
	if(A.mx > B.mx)
		return { A.mx, A.fmx, max(A.secmx, B.mx), A.s+B.s };
	else
		return { A.mx, A.fmx+B.fmx, max(A.secmx, B.secmx), A.s+B.s };
}

void refresh(int k){
	if(tag[k] >= t[k].mx)
		return (void)(tag[k] = inf);

	if(isLeaf[k]){
		t[k] = { tag[k], 1, 0, tag[k] };
		return (void)(tag[k] = inf);
	}
	if(tag[k] > t[k].secmx){
		t[k].s += (ll)t[k].fmx * (tag[k]-t[k].mx);
		t[k].mx = tag[k];
	}
	tag[k<<1] = min(tag[k<<1], tag[k]);
	tag[k<<1|1] = min(tag[k<<1|1], tag[k]);

	tag[k] = inf;
}


void build(int k, int l, int r, int *h){
	tag[k] = inf;

	if( l == r){
		t[k] = { h[l], 1, 0, h[l] };
		isLeaf[k] = true;
		return;
	}

	build(k << 1 , l , m(l,r) , h);
	build(k << 1 | 1, m(l,r)+1, r, h);

	t[k] = t[k<<1]+t[k<<1|1];
}

Node getNodeQuery(int k, int l, int r, int beg, int en){
	refresh(k);

	if(l >= beg && r <= en)
		return t[k];

	if(en <= m(l,r))
		return getNodeQuery(k<< 1 , l , m(l,r), beg, en );
	else if( beg > m(l,r) )
		return getNodeQuery(k << 1 |1 , m(l,r)+1, r, beg, en);

	return getNodeQuery(k << 1 , l , m(l,r), beg, en)+ getNodeQuery(k << 1|1,m(l,r)+1, r, beg, en);
}

void putTag(int k, int l, int r, int beg, int en, int val){
	refresh(k);

	if( l > en || r < beg || l > r || val > t[k].mx)
		return;

	if((l >= beg && r <= en && val > t[k].secmx) || l == r){
		tag[k] = val;
		refresh(k);
		return;
	}

	putTag(k << 1, l , m(l,r), beg, en, val);
	putTag(k << 1 | 1 , m(l,r)+1, r, beg, en, val);

	t[k] = t[k<<1]+t[k<<1|1];
}

int getIndex(int k, int l, int r, int beg, int en, int toCompare, int &qtt){
	refresh(k);

	if(t[k].mx < toCompare || l > en || r < beg)
		return 0;
	if(l >= beg && r <= en && t[k].fmx < qtt)
		return qtt -= t[k].fmx, 0;

	if( l == r )
		return qtt--, l;

	int al = getIndex(k << 1 , l , m(l,r), beg, en, toCompare, qtt);

	if(al)
		return al;

	return getIndex(k << 1 | 1, m(l,r)+1, r, beg, en, toCompare, qtt);
}

void printTree(int k, int l, int r){
	refresh(k);
	cout << l << " "  << r << " -> " << t[k].mx << " " << t[k].fmx << " " << t[k].secmx << endl;
	if( l == r) return;

	printTree(k << 1, l , m(l,r));
	printTree(k << 1 | 1, m(l,r)+1, r);
}

ll getAnswerQuery(int k, int l, int r, int beg, int en){
	refresh(k);

	if(l > en || r < beg)
		return 0;
	if(l >= beg && r <= en)
		return t[k].s;

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

	t[k] = t[k<<1]+t[k<<1|1];

	return al+ar;
}

void modifyPoint(int k, int l, int r, int id, int newVal){
	refresh(k);

	if(l == r)
		return (void)( t[k] = {newVal, 1, 0, newVal} );

	if(id <= m(l,r))
		modifyPoint(k<<1 , l , m(l,r), id, newVal);
	else
		modifyPoint(k << 1 | 1, m(l,r)+1, r, id, newVal);

	t[k] = t[k<<1]+t[k<<1|1];
}

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

	build(1,1,N, h);
}
void cut(int l, int r, int k) {
	while(k){
		Node ret = getNodeQuery(1,1,N, l, r);

		if(!ret.mx)
			return;

		ll credits = ret.mx - ret.secmx;
		credits *= ret.fmx;

		if(credits <= k){
			putTag(1,1,N, l, r ,ret.secmx);
			k -= credits;
			continue;
		}

		int m = k % ret.fmx;
		ll newVal = ret.mx - k/ret.fmx;

		int idx = m ? getIndex(1,1,N, l, r, ret.mx, m) : l-1;

		putTag(1,1,N, l,idx, newVal-1);
		putTag(1,1,N, idx+1, r, newVal);

		break;
	}

	/*cout << "after update, tree:\n";
	printTree(1,1,N);*/
}
void magic(int i, int x) {
	modifyPoint(1,1,N, i, x);
}
long long int inspect(int l, int r) {
	return getAnswerQuery(1,1,N, l, r);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 576 ms 40148 KB Output is correct
4 Correct 418 ms 40088 KB Output is correct
5 Correct 571 ms 40296 KB Output is correct
6 Correct 433 ms 40112 KB Output is correct
7 Correct 11 ms 10140 KB Output is correct
8 Correct 85 ms 9880 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10140 KB Output is correct
2 Correct 85 ms 9880 KB Output is correct
3 Incorrect 116 ms 38272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

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

Subtask #7
0 / 29.0

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