Submission #390745

#	Time	Username	Problem	Language	Result	Execution time	Memory
390745		SavicS	Watering can (POI13_kon)	C++14	100 / 100	461 ms	42016 KiB

kon

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10