oj.uz

Submission #831335

# Submission time Handle Problem Language Result Execution time Memory
831335 2023-08-20T06:00:53 Z ymm Distributing Candies (IOI21_candies) C++17
40 / 100
 1938 ms 15684 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("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.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 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1306 ms 13640 KB Output is correct
2 Correct 1261 ms 12964 KB Output is correct
3 Correct 1259 ms 12728 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 59 ms 8032 KB Output is correct
3 Correct 52 ms 7500 KB Output is correct
4 Correct 1259 ms 14752 KB Output is correct
5 Correct 1291 ms 15260 KB Output is correct
6 Incorrect 1257 ms 15684 KB Output isn't correct
7 Halted 0 ms 0 KB -

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 59 ms 7680 KB Output is correct
4 Correct 61 ms 5528 KB Output is correct
5 Correct 1874 ms 12428 KB Output is correct
6 Correct 1925 ms 13080 KB Output is correct
7 Correct 1921 ms 13560 KB Output is correct
8 Correct 1938 ms 12256 KB Output is correct
9 Correct 1681 ms 13832 KB Output is correct

Subtask #5
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 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1306 ms 13640 KB Output is correct
7 Correct 1261 ms 12964 KB Output is correct
8 Correct 1259 ms 12728 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 59 ms 8032 KB Output is correct
11 Correct 52 ms 7500 KB Output is correct
12 Correct 1259 ms 14752 KB Output is correct
13 Correct 1291 ms 15260 KB Output is correct
14 Incorrect 1257 ms 15684 KB Output isn't correct
15 Halted 0 ms 0 KB -