oj.uz

답안 #615508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
615508 2022-07-31T09:57:39 Z HamletPetrosyan 사탕 분배 (IOI21_candies) C++17
0 / 100
 383 ms 28416 KB 
#include "candies.h"

#include <vector>
#include <algorithm>
using namespace std;

#define ll long long
#define add push_back
#define pii pair<int, int>
#define len(a) ((int)(a).size())
#define all(a) a.begin(), a.end()

#define fr first
#define sc second

const int N = 3e5 + 5;

struct node{
	int l, r;
	int lv, mv, rv;
};

int C;
node t[4 * N];

int value(int num, node& a){
	if(num < a.l) return a.lv;
	if(num > a.r) return a.rv;
	return num + a.mv;
}

void merge(node& c, node& a, node& b){
	c.lv = value(a.lv, b);
	c.rv = value(a.rv, b);
	c.mv = a.mv + b.mv;

	c.l = max(b.lv - a.mv + 1, a.l);
	c.r = min(b.rv - a.mv - 1, a.r);
}

void build(int v, int tl, int tr){
	if(tl == tr){
		t[v].l = 0, t[v].r = 300000;
		t[v].lv = t[v].mv = t[v].rv = 0;
		return;
	}
	int tm = (tl + tr) / 2;
	build(2 * v, tl, tm);
	build(2 * v + 1, tm + 1, tr);
	merge(t[v], t[2 * v], t[2 * v + 1]);
}

void update(int v, int tl, int tr, int ind, int val){
	if(tl == tr){
		t[v].l = max(0, 0 - val); t[v].lv = 0;
		t[v].r = min(C, C - val); t[v].rv = C;
		t[v].mv = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if(ind <= tm) update(2 * v, tl, tm, ind, val);
	else update(2 * v + 1, tm + 1, tr, ind, val);
	merge(t[v], t[2 * v], t[2 * v + 1]);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    C = c[0];
	vector<pii> x;
	vector<int> ret;
	for(int i = 0; i < len(l); i++){
		x.add({l[i], -(i + 1)});
		x.add({r[i], +(i + 1)});
	}
	sort(all(x));
	build(1, 1, len(v));
	int ind = 0;
	for(int i = 0; i < len(x); i++){
		while(ind < len(x) && x[ind].fr == i && x[ind].sc < 0){
			update(1, 1, len(v), -x[ind].sc, v[-x[ind].sc - 1]);
			ind++;
		}
		ret.add(value(0, t[1]));
		while(ind < len(x) && x[ind].fr == i && x[ind].sc > 0){
			update(1, 1, len(v), x[ind].sc, 0);
			ind++;
		}
	}
    return ret;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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