제출 #478447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
478447		super_j6	사탕 분배 (IOI21_candies)	C++17	100 / 100	1053 ms	49376 KiB

candies

//#include "candies.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
#define vi vector<int>

const ll inf = 0x3f3f3f3f3f3f3f3f;

struct segTree{
	int l, r;
	segTree *tl, *tr;
	ll ss, mn, mx;
	
	segTree(int l, int r) : l(l), r(r){
		ss = mn = mx = 0;
		if(l != r){
			int mid = l + (r - l) / 2;
			tl = new segTree(l, mid);
			tr = new segTree(mid + 1, r);
		}
	}
	
	void add(int x, ll y){
		if(x < l || r < x) return;
		if(l == r) return (void)(ss += y, mn += y, mx += y);
		tl->add(x, y), tr->add(x, y);
		ss = tl->ss + tr->ss;
		mn = min(tl->mn + tr->ss, tr->mn);
		mx = max(tl->mx + tr->ss, tr->mx);
	}
	
	ll qry(ll x){
		if(l == r) return ss;
		return tr->mx <= x ? min(tl->qry(x - tr->ss) + tr->ss, tr->mn) : tr->qry(x);
	}
};

const int mxn = 200001;
int n, q;
vi b[mxn];

vi distribute_candies(vi a, vi l, vi r, vi v){
	n = a.size(), q = l.size();
	for(int i = 0; i < q; i++){
		b[l[i]].push_back(i + 1);
		b[r[i] + 1].push_back(-i - 1);
	} 
	
	vi f(n);
	segTree tre(-2, q - 1);
	tre.add(-2, inf), tre.add(-1, -inf);
	for(int i = 0; i < n; i++){
		for(int j : b[i]) tre.add(abs(j) - 1, j / abs(j) * v[abs(j) - 1]);
		int l = -1, r = a[i];
		while(r - l > 1){
			int mid = (l + r) / 2;
			if(mid - tre.qry(mid) < a[i]) l = mid;
			else r = mid;
		}
		f[i] = r;
	}
	
	return f;
}

int fufu(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, q;
	cin >> n >> q;
	
	vi a(n), l(q), r(q), v(q);
	
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < q; i++) cin >> l[i] >> r[i] >> v[i];
	
	vi f = distribute_candies(a, l, r, v);
	
	cout << f[0];
	for(int i = 1; i < n; i++) cout << " " << f[i];
	cout << endl;
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:34:17: warning: 'tre.segTree::tr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |   ss = tl->ss + tr->ss;
      |                 ^~
candies.cpp:57:10: note: 'tre.segTree::tr' was declared here
   57 |  segTree tre(-2, q - 1);
      |          ^~~
candies.cpp:34:17: warning: 'tre.segTree::tl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |   ss = tl->ss + tr->ss;
      |                 ^~
candies.cpp:57:10: note: 'tre.segTree::tl' was declared here
   57 |  segTree tre(-2, q - 1);
      |          ^~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33