oj.uz

답안 #940648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
940648 2024-03-07T12:38:04 Z 7mody 사탕 분배 (IOI21_candies) C++17
0 / 100
 97 ms 18548 KB 
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 


int j, n, m;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
    n = c.size();
    m = r.size();

    // vector<vector<int>> L(n),R(n);

    // for(int i=0; i < m;i++){
    //     L[l[i]].push_back(i);
    //     R[r[i]].push_back(i);
    // }


    // for(int i=0; i < n;i++){

    //     for(int x : L[i]) st.update(x, n, v[x]);
    // }

    vector<int> s(n);
    vector<array<ll,3>> arr(m + 4, {0, ll(-1e18), ll(1e18)});
    vector<ll> pre(m + 4);
    arr[0] = {0,0,0};
    // sum, maximum, minimum

    for(int i=1; i <= m;i++){
        arr[i+1][0] = v[i-1] + arr[i][0];
    }

    for(int i = m + 1; i >= 1;i--){
        arr[i][1] = max(arr[i][0], arr[i+1][1]);
        arr[i][2] = min(arr[i][0], arr[i+1][2]);
    }
    int limit = 1e18;
    int tp;
    for(int i = 1; i <= m;i++){
        pre[i+1] = pre[i] + v[i-1];
        if(limit > pre[i+1]){
            tp = i + 1;
            limit = pre[i+1];
        }
    }

    // for(int i=1; i <= m + 1;i++) cout << arr[i][1] << ' '; cout << endl;

    for(int i=0; i < n;i++){
        int l = 0;
        int r = m;
        int id = -1;

        while(l <= r){
            int mid = (l+r)/2;
            if(arr[mid + 1][1] - arr[mid + 1][2] >= c[i]){
                l = mid+1;
                id = mid;
            } else r = mid-1;
        }
        if(id == -1){
            s[i] = pre[m+1] - pre[tp];
            continue;
        }
        int cond = 0;
        id++;
        if(arr[id][1] == arr[id+1][1]) cond = 1;
        else cond = 0;
        if(cond){
            ll curr = arr[id][1];
            int l = id - 1;
            int r = m;
            while(l <= r){
                int mid = (l+r)/2;
                if(arr[mid + 1][1] == curr){
                    id = mid;
                    l = mid + 1;
                } else r = mid - 1;
            }
            id++;
            s[i] = c[i] - (arr[id][0] - arr[m+1][0]);
        } else{
            ll curr = arr[id][2];
            int l = id - 1;
            int r = m;
            while(l <= r){
                int mid = (l+r)/2;
                if(arr[mid + 1][2] == curr){
                    id = mid;
                    l = mid + 1;
                } else r = mid - 1;
            }
            id++;
            s[i] = arr[m+1][0] - arr[id][0];
        }
    }
    return s;
}

// void solve(){
//     cin >> n;
//     vector<int> c(n);
//     for(int i=0; i < n;i++) cin >> c[i];
//     int q; cin >> q;
//     vector<int> l(q),r(q),v(q);
//     for(int i=0; i < q;i++) cin >> l[i];
//     for(int i=0; i < q;i++) cin >> r[i];
//     for(int i=0; i < q;i++) cin >> v[i];
//     vector<int> ans = distribute_candies(c,l,r,v); cout << endl;
//     for(int x : ans) cout << x << ' '; cout << endl;
// }

// int32_t main(){
//     ios::sync_with_stdio(false);    
//     cin.tie();
//     cout.tie();
//     int t=1;
//     // cin >> t;
//     while(t--){
//         // cout << t <<  ":\n";
//         solve();
//     }
// }

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:41:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   41 |     int limit = 1e18;
      |                 ^~~~
candies.cpp:66:37: warning: 'tp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |             s[i] = pre[m+1] - pre[tp];
      |                                     ^

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 97 ms 18548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -