oj.uz

답안 #478375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
478375 2021-10-07T06:14:04 Z super_j6 사탕 분배 (IOI21_candies) C++17
0 / 100
 960 ms 47600 KB 
#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 main(){
	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;
}*/

Compilation message

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
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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