Submission #1046457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046457		ymm	Distributing Candies (IOI21_candies)	C++17	100 / 100	1321 ms	15700 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#define INLINE __attribute__((always_inline)) constexpr
#define ASSUME(expr) __attribute__((assume(expr)))
#define MAX(x, y) ((x)>(y)?(x):(y))
#define MIN(x, y) ((x)<(y)?(x):(y))

INLINE int uppos(int x, int u) { return x; }
INLINE int upneg(int x, int u) { return x; }
template<class... T> INLINE int uppos(int x, int u, int v, T... vs);
template<class... T> INLINE int upneg(int x, int u, int v, T... vs);

template<class... T>
INLINE int uppos(int x, int u, int v, T... vs)
{
	ASSUME(0 <= x && x <= u && v > 0);
	return upneg(MIN(x + v, u), u, vs...);
}

template<class... T>
INLINE int upneg(int x, int u, int v, T... vs)
{
	ASSUME(0 <= x && x <= u && v > 0);
	return uppos(MAX(x - v, 0), u, vs...);
}

const int N = 200'010;
const int S = 1024;
int a[N], b[N];

template<bool start_neg, class... T>
void uprange(int l, int r, T... v)
{
	if constexpr(start_neg) {
		Loop (i,l,r)
			a[i] = upneg(a[i], b[i], v...);
	} else {
		Loop (i,l,r)
			a[i] = uppos(a[i], b[i], v...);
	}
}

const int M = 4;

template<bool start_neg>
void up(int l, int r, vector<int> vec)
{
	switch (vec.size()) {
	case 0: break;
	case 1: uprange<start_neg>(l, r, vec[0]); break;
	case 2: uprange<start_neg>(l, r, vec[0], vec[1]); break;
	case 3: uprange<start_neg>(l, r, vec[0], vec[1], vec[2]); break;
	case 4: uprange<start_neg>(l, r, vec[0], vec[1], vec[2], vec[3]); break;
	default: assert(false);
	}
}

const int inf = 1e9 + 10;

std::vector<int> distribute_candies(std::vector<int> _c, std::vector<int> ql,
                                    std::vector<int> qr, std::vector<int> qv) {
	int n = _c.size();
	int q = ql.size();
	for (int &x : qr)
		++x;
	Loop (i,0,n)
		b[i] = _c[i];
	for (int L = 0; L < n; L += S) {
		int R = min(L + S, n);
		vector<int> vec;
		bool st = 0, ls = 0;
		auto flush = [&]() {
			if (vec.empty())
				return;
			(st? up<true>: up<false>)(L, R, vec);
			vec.clear();
		};
		Loop (i,0,q) {
			int l = MAX(ql[i], L);
			int r = MIN(qr[i], R);
			if (l >= r)
				continue;
			if (L == l && R == r) {
				if (!vec.size()) {
					vec.push_back(abs(qv[i]));
					st = ls = qv[i] < 0;
				} else if (ls == (qv[i] < 0)) {
					vec.back() = min(inf, vec.back() + abs(qv[i]));
				} else {
					vec.push_back(abs(qv[i]));
					ls = !ls;
				}
			} else {
				flush();
				(qv[i] < 0? uprange<true, int>: uprange<false, int>)(l, r, abs(qv[i]));
			}
			if (vec.size() == M)
				flush();
		}
		flush();
	}
	return vector<int>(a, a+n);
}

Compilation message (stderr)

candies.cpp: In function 'constexpr int uppos(int, int, int, T ...)':
candies.cpp:11:22: warning: attributes at the beginning of statement are ignored [-Wattributes]
   11 | #define ASSUME(expr) __attribute__((assume(expr)))
      |                      ^~~~~~~~~~~~~
candies.cpp:23:2: note: in expansion of macro 'ASSUME'
   23 |  ASSUME(0 <= x && x <= u && v > 0);
      |  ^~~~~~
candies.cpp: In function 'constexpr int upneg(int, int, int, T ...)':
candies.cpp:11:22: warning: attributes at the beginning of statement are ignored [-Wattributes]
   11 | #define ASSUME(expr) __attribute__((assume(expr)))
      |                      ^~~~~~~~~~~~~
candies.cpp:30:2: note: in expansion of macro 'ASSUME'
   30 |  ASSUME(0 <= x && x <= u && v > 0);
      |  ^~~~~~

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