Submission #481490

#	Time	Username	Problem	Language	Result	Execution time	Memory
481490		8e7	사탕 분배 (IOI21_candies)	C++17	29 / 100	116 ms	14400 KiB

candies

//Challenge: Accepted
#include "candies.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b) {
	cout << a << " ", debug(b ...);
};
template<class T> void pary (T l, T r) {
	while (l!= r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 200005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = v.size();
	vector<int> ret(n, 0);
	vector<pii> seg;
	for (int i = 0;i < q;i++) {
		if (v[i] >= 0) {
			int tot = 0;
			while (seg.size() && tot + seg.back().ss - seg.back().ff + v[i] >= seg.back().ss) {
				tot += seg.back().ss - seg.back().ff;
				seg.pop_back();	
			}	
			seg.push_back({0, tot + v[i]});
		} else {
			v[i] = -v[i];
			int cur = 0;
			while (seg.size() && cur < v[i]) {
				if (cur + seg.back().ss - seg.back().ff <= v[i]) {
					cur += seg.back().ss - seg.back().ff;
					seg.pop_back();
				} else {
					seg.back().ff += v[i] - cur;
					cur = v[i];
					break;
				}
			}
		}
		//for (auto p:seg) debug(p.ff, p.ss);
		//debug();
	}
	vector<pii> a(n);
	for (int i = 0;i < n;i++) a[i] = {c[i], i};
	sort(a.begin(), a.end());
	reverse(seg.begin(), seg.end());
	int ind = 0, sum = 0;
	for (int i = 0;i < n;i++) {
		bool type = 0;
		while (ind < seg.size() && seg[ind].ff <= a[i].ff) {
			if (seg[ind].ss <= a[i].ff) {
				sum += seg[ind].ss - seg[ind].ff;
				ind++;
			} else {
				type = 1;
				ret[a[i].ss] = sum + a[i].ff - seg[ind].ff;
				break;
			}	
		}	
		if (!type) ret[a[i].ss] = sum;
	}
	return ret;
}
/*
6
0 6 8 9 3 1
5
0 4 4
0 4 -2
0 4 3
0 4 -6
0 4 2
*/

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   while (ind < seg.size() && seg[ind].ff <= a[i].ff) {
      |          ~~~~^~~~~~~~~~~~

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