oj.uz

Submission #481490

# Submission time Handle Problem Language Result Execution time Memory
481490 2021-10-21T03:23:02 Z 8e7 Distributing Candies (IOI21_candies) C++17
29 / 100
 116 ms 14400 KB 
//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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 10416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 50 ms 5092 KB Output is correct
4 Correct 78 ms 5960 KB Output is correct
5 Correct 104 ms 10588 KB Output is correct
6 Correct 112 ms 14364 KB Output is correct
7 Correct 116 ms 14400 KB Output is correct
8 Correct 111 ms 13860 KB Output is correct
9 Correct 101 ms 14372 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -