oj.uz

답안 #390745

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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