oj.uz

답안 #598730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
598730 2022-07-18T20:49:39 Z CaroLinda Weirdtree (RMI21_weirdtree) C++14
0 / 100
 2000 ms 37440 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] == inf)
		return;

	if(isLeaf[k]){
		t[k] = {min(t[k].mx, tag[k]), 1, 0, min(t[k].mx, tag[k])};
	}
	else if( tag[k] > t[k].secmx ){
		t[k].s += 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]);
	}
	else if(tag[k] <= t[k].secmx){
		tag[k << 1] = min(tag[k << 1], tag[k]);
		tag[k << 1 | 1] = min(tag[k << 1 | 1], tag[k]);

		refresh(k << 1);
		refresh(k << 1 | 1);

		t[k] = t[k<<1]+t[k<<1|1];
	}
	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)
		return;

	if( l == r){
		tag[k]= val;
		refresh(k);
		return;
	}

	if(l >= beg && r <= en && val > t[k].secmx){
		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);

	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);

	/*cout << "Printing tree after building\n";
	printTree(1,1,N);*/
}
void cut(int l, int r, int k) {
	/*cout << "printing tree before query\n";
	printTree(1,1,N);*/

	while(k){
		Node ret = getNodeQuery(1,1,N, l, r);

	//cout << ret.mx << " " << ret.fmx << " " << ret.secmx << " from " << l << " " << r << " " << k << endl;

		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);


		return;
	}
}
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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2083 ms 37440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -