Submission #831335

#	Time	Username	Problem	Language	Result	Execution time	Memory
831335		ymm	Distributing Candies (IOI21_candies)	C++17	40 / 100	1938 ms	15684 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("avx")

const int inf = 1e9+1;
const int N = 200'010;
const int S = 2048;
int a[N], c[N];

void add(int l, int r, int x)
{
	Loop (i,l,r)
		a[i] = (a[i] + x > c[i]? c[i]: a[i] + x);
}
void sub(int l, int r, int x)
{
	Loop (i,l,r)
		a[i] = (a[i] - x < 0? 0: a[i] - x);
}
void addsub(int l, int r, int x, int y)
{
	Loop (i,l,r) {
		a[i] = (a[i] + x > c[i]? c[i]: a[i] + x);
		a[i] = (a[i] - y < 0? 0: a[i] - y);
	}
}
void subadd(int l, int r, int x, int y)
{
	Loop (i,l,r) {
		a[i] = (a[i] - x < 0? 0: a[i] - x);
		a[i] = (a[i] + y > c[i]? c[i]: a[i] + y);
	}
}
void addsubadd(int l, int r, int x, int y, int z)
{
	Loop (i,l,r) {
		a[i] = (a[i] + x > c[i]? c[i]: a[i] + x);
		a[i] = (a[i] - y < 0? 0: a[i] - y);
		a[i] = (a[i] + z > c[i]? c[i]: a[i] + z);
	}
}
void subaddsub(int l, int r, int x, int y, int z)
{
	Loop (i,l,r) {
		a[i] = (a[i] - x < 0? 0: a[i] - x);
		a[i] = (a[i] + y > c[i]? c[i]: a[i] + y);
		a[i] = (a[i] - z < 0? 0: a[i] - z);
	}
}
void up(int l, int r, int x)
{
	if (x > 0)
		add(l, r, x);
	else
		sub(l, r, -x);
}
void upup(int l, int r, int x, int y)
{
	if (x >  0 && y >  0)
		add(l, r, min(inf, x+y));
	if (x <= 0 && y <= 0)
		sub(l, r, min(inf, -(x+y)));
	if (x >  0 && y <= 0)
		addsub(l, r, x, -y);
	if (x <= 0 && y >  0)
		subadd(l, r, -x, y);
}
void upupup(int l, int r, int x, int y, int z)
{
	if ((x > 0) == (y > 0))
		return upup(l, r, clamp(-inf, x+y, inf), z);
	if ((y > 0) == (z > 0))
		return upup(l, r, x, clamp(-inf, y+z, inf));
	if (x > 0)
		addsubadd(l, r, x, -y, z);
	if (x <= 0)
		subaddsub(l, r, -x, y, -z);
}
void upv(int l, int r, int *a, int cnt)
{
	switch (cnt) {
	case 0: return;
	case 1: return up(l, r, a[0]);
	case 2: return upup(l, r, a[0], a[1]);
	case 3: return upupup(l, r, a[0], a[1], a[2]);
	}
}

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)
	    c[i] = _c[i];
    for (int L = 0; L < n; L += S) {
	    int R = min<int>(L+S, n);
	    for (int i = 0; i < q;) {
		    int cnt;
		    for (cnt = 0; cnt < 3 && i+cnt < q; ++cnt) {
			    if (!(ql[i+cnt] <= L && R <= qr[i+cnt]))
				    break;
		    }
		    upv(L, R, &qv[i], cnt);
		    i += cnt;
		    if (cnt != 3 && i != q) {
			    up(max(ql[i], L), min(qr[i], R), qv[i]);
			    i += 1;
		    }
	    }
    }
    return vector<int>(a, a+n);
}

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