oj.uz

답안 #617479

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
617479 2022-08-01T11:40:31 Z amunduzbaev 사탕 분배 (IOI21_candies) C++17
27 / 100
 703 ms 34596 KB 
#include "candies.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

typedef long long ll;

const ll inf = 1e18;
const int N = 2e5 + 5;

struct ST{
	ll mn[N << 2], mx[N << 2]; //, mn2[N << 2], mx2[N << 2];
	ll p[N << 2], umn[N << 2], umx[N << 2];
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		mn[x << 1] += p[x], mx[x << 1] += p[x], p[x << 1] += p[x];
		mn[x << 1 | 1] += p[x], mx[x << 1 | 1] += p[x], p[x << 1 | 1] += p[x];
		
		if(umn[x]){
			mn[x << 1] = min(mn[x << 1], mx[x]);
			mn[x << 1 | 1] = min(mn[x << 1 | 1], mx[x]);
			mx[x << 1] = min(mx[x << 1], mx[x]);
			mx[x << 1 | 1] = min(mx[x << 1 | 1], mx[x]);
			umn[x << 1] = umn[x << 1 | 1] = 1;
		}
		
		if(umx[x]){
			mn[x << 1] = max(mn[x << 1], mn[x]);
			mn[x << 1 | 1] = max(mn[x << 1 | 1], mn[x]);
			mx[x << 1] = max(mx[x << 1], mn[x]);
			mx[x << 1 | 1] = max(mx[x << 1 | 1], mn[x]);
			umx[x << 1] = umx[x << 1 | 1] = 1;
		}
		
		p[x] = umn[x] = umx[x] = 0;
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			mn[x] += v, mx[x] += v; // , mn2[x] += v, mx2[x] += v;
			p[x] += v;
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x << 1);
		add(l, r, v, m + 1, rx, x << 1 | 1);
		mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	
	void umin(int l, int r, ll v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			mn[x] = min(mn[x], v);
			mx[x] = min(mx[x], v);
			umn[x] = 1;
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		umin(l, r, v, lx, m, x << 1);
		umin(l, r, v, m + 1, rx, x << 1 | 1);
		mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	
	void umax(int l, int r, ll v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			mn[x] = max(mn[x], v);
			mx[x] = max(mx[x], v);
			umx[x] = 1;
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		umax(l, r, v, lx, m, x << 1);
		umax(l, r, v, m + 1, rx, x << 1 | 1);
		mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	
	ll get(int i, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return mx[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		if(i <= m) return get(i, lx, m, x << 1);
		else return get(i, m + 1, rx, x << 1 | 1);
	}
}tree;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n = c.size();
	int q = l.size();
	
	
	
	for(int i=0;i<q;i++){
		tree.add(l[i], r[i], v[i]);
		tree.umin(l[i], r[i], c[0]);
		tree.umax(l[i], r[i], 0);
		//~ add(l[i], r[i], v[i]);
		//~ umin(l[i], r[i], c[0]);
		//~ umax(l[i], r[i], 0);
	}
	
	vector<int> a(n);
	for(int i=0;i<n;i++){
		a[i] = tree.get(i);
	}
	
	return a;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 346 ms 7044 KB Output is correct
3 Correct 119 ms 25916 KB Output is correct
4 Correct 651 ms 29552 KB Output is correct
5 Correct 703 ms 34208 KB Output is correct
6 Correct 703 ms 34596 KB Output is correct
7 Correct 647 ms 33940 KB Output is correct

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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