oj.uz

답안 #828741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828741 2023-08-17T14:46:56 Z fatemetmhr 사탕 분배 (IOI21_candies) C++17
38 / 100
 5000 ms 12424 KB 
//#pragma GCC optimize ("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops,O3")

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define debug(x)  cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)    x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi        first
#define se        second
#define pb        push_back
#define mp        make_pair

const int ss    = 1500;
const int maxn5 = 2e5 + 10;

int ret[maxn5], c[maxn5], sig[maxn5];
int L[maxn5], R[maxn5], V[maxn5];

std::vector<int> distribute_candies(std::vector<int> C, std::vector<int> LL,
                                    std::vector<int> RR, std::vector<int> VV) {
    int n = C.size(), q = LL.size();
    for(int i = 0; i < n; i++)
        c[i] = C[i];
    for(int i = 0; i < q; i++){
        L[i] = LL[i];
        R[i] = RR[i];
        V[i] = VV[i];
        sig[i] = (V[i] > 0 ? 1 : -1);
    }
    for(int tt = 0; tt < n; tt += ss){
        for(int i = 1; i < q; i += 2){
            int lim = MIN(tt + ss, n);
            ll v1 = V[i - 1], v2 = V[i];
            if(MAX(L[i], L[i - 1] > tt || MIN(R[i], R[i - 1]) < lim - 1)){
                int l = MAX(tt, L[i - 1]), r = MIN(lim, R[i - 1] + 1);
                for(int j = l; j < r; j++){
                    ret[j] += v1;
                    ret[j] = (ret[j] < 0 ? 0 : (ret[j] > c[j] ? c[j] : ret[j]));
                }
                l = MAX(tt, L[i]); 
                r = MIN(lim, R[i] + 1);
                for(int j = l; j < r; j++){
                    ret[j] += v2;
                    ret[j] = (ret[j] < 0 ? 0 : (ret[j] > c[j] ? c[j] : ret[j]));
                }
            }
            else{
                if(sig[i] == sig[i - 1]){
                    v1 += v2;
                    if(v1 > 0){
                        for(int i = tt; i < lim; i++){
                            ret[i] = MIN(c[i], ret[i] + v1);
                        }
                    }
                    else{
                        for(int i = tt; i < lim; i++){
                            ret[i] = MAX(0, ret[i] + v1);
                        }
                    }
                }
                else{
                    for(int j = tt; j < lim; j++){
                        ret[j] += v1;
                        ret[j] = (ret[j] < 0 ? 0 : (ret[j] > c[j] ? c[j] : ret[j]));
                        ret[j] += v2;
                        ret[j] = (ret[j] < 0 ? 0 : (ret[j] > c[j] ? c[j] : ret[j]));
                    }
                }
            }
        }
    }
    if(q & 1){
        for(int i = L[q - 1]; i <= R[q - 1]; i++){
            ret[i] += V[q - 1];
            ret[i] = (ret[i] < 0 ? 0 : (ret[i] > c[i] ? c[i] : ret[i]));
        }
    }

    std::vector<int> s;
    for(int i = 0; i < n; i++)
        s.pb(ret[i]);
    return s;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 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 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2716 ms 12368 KB Output is correct
2 Correct 2693 ms 12376 KB Output is correct
3 Correct 2677 ms 12348 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 74 ms 8172 KB Output is correct
3 Correct 75 ms 5520 KB Output is correct
4 Correct 2727 ms 12424 KB Output is correct
5 Correct 2725 ms 12380 KB Output is correct
6 Correct 2692 ms 12360 KB Output is correct
7 Correct 2683 ms 12388 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 122 ms 8168 KB Output is correct
4 Correct 119 ms 4624 KB Output is correct
5 Execution timed out 5059 ms 10972 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 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 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2716 ms 12368 KB Output is correct
7 Correct 2693 ms 12376 KB Output is correct
8 Correct 2677 ms 12348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 74 ms 8172 KB Output is correct
11 Correct 75 ms 5520 KB Output is correct
12 Correct 2727 ms 12424 KB Output is correct
13 Correct 2725 ms 12380 KB Output is correct
14 Correct 2692 ms 12360 KB Output is correct
15 Correct 2683 ms 12388 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 122 ms 8168 KB Output is correct
19 Correct 119 ms 4624 KB Output is correct
20 Execution timed out 5059 ms 10972 KB Time limit exceeded
21 Halted 0 ms 0 KB -