oj.uz

답안 #826823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
826823 2023-08-16T05:02:54 Z ymm 사탕 분배 (IOI21_candies) C++17
100 / 100
 2612 ms 8964 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 = 1024;
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 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);
}

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;
    if (q%2) {
	    ql.push_back(0);
	    qr.push_back(1);
	    qv.push_back(0);
	    ++q;
    }
    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; i += 2) {
		    int l0 = ql[i], l1 = ql[i+1];
		    int r0 = qr[i], r1 = qr[i+1];
		    int v0 = qv[i], v1 = qv[i+1];
		    if (l0 <= L && R <= r0 && l1 <= L && R <= r1) {
			    upup(L, R, v0, v1);
		    } else {
			    up(max(l0, L), min(r0, R), v0);
			    up(max(l1, L), min(r1, R), v1);
		    }
	    }
    }
    return vector<int>(a, a+n);
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 248 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1628 ms 8896 KB Output is correct
2 Correct 1545 ms 8900 KB Output is correct
3 Correct 1548 ms 8924 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 66 ms 4968 KB Output is correct
3 Correct 72 ms 5324 KB Output is correct
4 Correct 1564 ms 8864 KB Output is correct
5 Correct 1556 ms 8908 KB Output is correct
6 Correct 2155 ms 8828 KB Output is correct
7 Correct 1584 ms 8912 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 66 ms 4984 KB Output is correct
4 Correct 60 ms 4360 KB Output is correct
5 Correct 2507 ms 8908 KB Output is correct
6 Correct 2503 ms 8908 KB Output is correct
7 Correct 2612 ms 8964 KB Output is correct
8 Correct 2525 ms 8908 KB Output is correct
9 Correct 2502 ms 8896 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 248 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1628 ms 8896 KB Output is correct
7 Correct 1545 ms 8900 KB Output is correct
8 Correct 1548 ms 8924 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 66 ms 4968 KB Output is correct
11 Correct 72 ms 5324 KB Output is correct
12 Correct 1564 ms 8864 KB Output is correct
13 Correct 1556 ms 8908 KB Output is correct
14 Correct 2155 ms 8828 KB Output is correct
15 Correct 1584 ms 8912 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 66 ms 4984 KB Output is correct
19 Correct 60 ms 4360 KB Output is correct
20 Correct 2507 ms 8908 KB Output is correct
21 Correct 2503 ms 8908 KB Output is correct
22 Correct 2612 ms 8964 KB Output is correct
23 Correct 2525 ms 8908 KB Output is correct
24 Correct 2502 ms 8896 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 49 ms 4168 KB Output is correct
27 Correct 63 ms 4980 KB Output is correct
28 Correct 1518 ms 8908 KB Output is correct
29 Correct 1562 ms 8924 KB Output is correct
30 Correct 1555 ms 8812 KB Output is correct
31 Correct 1531 ms 8888 KB Output is correct
32 Correct 1521 ms 8868 KB Output is correct