oj.uz

Submission #831343

# Submission time Handle Problem Language Result Execution time Memory
831343 2023-08-20T06:22:03 Z ymm Distributing Candies (IOI21_candies) C++17
100 / 100
 3068 ms 14932 KB 
#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")

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(x+y, -inf, inf), z);
	if ((y > 0) == (z > 0))
		return upup(l, r, x, clamp(y+z, -inf, 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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1275 ms 9660 KB Output is correct
2 Correct 1267 ms 9688 KB Output is correct
3 Correct 1267 ms 9580 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 77 ms 5708 KB Output is correct
3 Correct 50 ms 6060 KB Output is correct
4 Correct 1315 ms 9684 KB Output is correct
5 Correct 1317 ms 9604 KB Output is correct
6 Correct 1330 ms 9624 KB Output is correct
7 Correct 1282 ms 14932 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 71 ms 5808 KB Output is correct
4 Correct 66 ms 5136 KB Output is correct
5 Correct 3068 ms 9624 KB Output is correct
6 Correct 3057 ms 9692 KB Output is correct
7 Correct 3056 ms 9656 KB Output is correct
8 Correct 3035 ms 9676 KB Output is correct
9 Correct 2896 ms 9668 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1275 ms 9660 KB Output is correct
7 Correct 1267 ms 9688 KB Output is correct
8 Correct 1267 ms 9580 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 77 ms 5708 KB Output is correct
11 Correct 50 ms 6060 KB Output is correct
12 Correct 1315 ms 9684 KB Output is correct
13 Correct 1317 ms 9604 KB Output is correct
14 Correct 1330 ms 9624 KB Output is correct
15 Correct 1282 ms 14932 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 71 ms 5808 KB Output is correct
19 Correct 66 ms 5136 KB Output is correct
20 Correct 3068 ms 9624 KB Output is correct
21 Correct 3057 ms 9692 KB Output is correct
22 Correct 3056 ms 9656 KB Output is correct
23 Correct 3035 ms 9676 KB Output is correct
24 Correct 2896 ms 9668 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 48 ms 5428 KB Output is correct
27 Correct 70 ms 7636 KB Output is correct
28 Correct 1328 ms 13500 KB Output is correct
29 Correct 1325 ms 13788 KB Output is correct
30 Correct 1297 ms 14068 KB Output is correct
31 Correct 1296 ms 14188 KB Output is correct
32 Correct 1323 ms 14416 KB Output is correct