Submission #390745

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
390745	2021-04-16T20:28:51 Z	SavicS	Watering can (POI13_kon)	C++14	100 / 100	461 ms	42016 KB

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,int> pii;
const int maxn = 300005;
const ll inf = 1e18 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)


int N, K;
int niz[maxn];

pii bor[4 * maxn];
ll lenj[4 * maxn];
void build(int v, int tl, int tr) {
	if(tl == tr) {
		bor[v] = {niz[tl], tl};
		return;
	}
	int mid = (tl + tr) / 2;
	build(v * 2, tl, mid);
	build(v * 2 + 1, mid + 1, tr);
	bor[v] = max(bor[v * 2], bor[v * 2 + 1]);
}

void propagate(int v, int tl, int tr) {
	if(lenj[v]) {
		bor[v].fi += lenj[v];
		if(tl != tr) {
			lenj[2 * v] += lenj[v];
			lenj[2 * v + 1] += lenj[v];
		}
		lenj[v] = 0;
	}
}

void lazyupd(int v, int tl, int tr, int l, int r, ll val) {
	propagate(v, tl, tr);
	if(tl > tr || tl > r || tr < l)return;
	if(tl >= l && tr <= r) {
		bor[v].fi += val;
		if(tl != tr) {
			lenj[v * 2] += val;
			lenj[v * 2 + 1] += val;
		}
		return;
	}
	int mid = (tl + tr) / 2;
	lazyupd(v * 2, tl, mid, l, r, val);
	lazyupd(v * 2 + 1, mid + 1, tr, l, r, val);
	bor[v] = max(bor[v * 2], bor[v * 2 + 1]);
}

int dud[maxn];
void upd(int x, int val) {
	while(x <= maxn) {
		dud[x] += val;
		x += x&(-x);
	}
}
int query(int x) {
	int sum = 0;
	while(x > 0) {
		sum += dud[x];
		x -= x&(-x);
	}
	return sum;
}


void inicjuj(int n, int k, int *D) {
	N = n, K = k;
	ff(i,1,n)niz[i] = D[i - 1];

	build(1,1,N);
	while(bor[1].fi >= K) {

		upd(bor[1].se, 1);
		lazyupd(1,1,N,bor[1].se,bor[1].se, -inf);

	}


}

void podlej(int a, int b) {
	a += 1, b += 1;
	lazyupd(1,1,N,a,b,1);

	while(bor[1].fi >= K) {

		upd(bor[1].se, 1);
		lazyupd(1,1,N,bor[1].se, bor[1].se, -inf);

	}

}


int dojrzale(int a, int b) {
	a += 1, b += 1;
	return query(b) - query(a - 1);
}

//int main() 
//{
//	ios::sync_with_stdio(false);
//	cout.tie(nullptr);
//	cin.tie(nullptr);
//
//	int n, k;
//	cin >> n >> k;
//	int a[n];
//	ff(i,0,n - 1)cin >> a[i];
//
//	inicjuj(n, k, a);
//
//	cout << dojrzale(2, 3) << endl;
//	podlej(0, 2);
//	cout << dojrzale(1, 2) << endl;
//	podlej(2, 3);
//	podlej(0, 1);
//	cout << dojrzale(0, 3) << endl;
//
//
//	return 0;
//}
///**
//
//4 6
//5 4 3 7
//
//// probati bojenje sahovski ili slicno
//
//**/

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	460 KB	Output is correct
2	Correct	4 ms	588 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	3932 KB	Output is correct
2	Correct	52 ms	3652 KB	Output is correct
3	Correct	38 ms	3512 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	6144 KB	Output is correct
2	Correct	87 ms	6400 KB	Output is correct
3	Correct	72 ms	6336 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	10928 KB	Output is correct
2	Correct	95 ms	10564 KB	Output is correct
3	Correct	98 ms	7800 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	213 ms	15044 KB	Output is correct
2	Correct	134 ms	12744 KB	Output is correct
3	Correct	186 ms	13588 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	266 ms	15300 KB	Output is correct
2	Correct	226 ms	20024 KB	Output is correct
3	Correct	222 ms	14372 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	346 ms	25192 KB	Output is correct
2	Correct	443 ms	23620 KB	Output is correct
3	Correct	346 ms	26568 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	461 ms	40900 KB	Output is correct
2	Correct	333 ms	40508 KB	Output is correct
3	Correct	403 ms	38208 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	440 ms	41320 KB	Output is correct
2	Correct	397 ms	42016 KB	Output is correct
3	Correct	391 ms	39056 KB	Output is correct

Submission #390745

Compilation message