oj.uz

답안 #1069443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069443 2024-08-21T23:56:02 Z ArthuroWich 사탕 분배 (IOI21_candies) C++17
0 / 100
 865 ms 30472 KB 
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int segs[4*200005], segmx[4*200005], segmn[4*200005], lazy[4*200005];
void lazypropagate(int n, int l, int r) {
    if (lazy[n]) {
        segmn[n] += lazy[n];
        segmx[n] += lazy[n];
        if (l != r) {
            lazy[2*n] += lazy[n];
            lazy[2*n+1] += lazy[n];
        }
        lazy[n] = 0;
    }
}
void updates(int n, int l, int r, int i, int v) {
    if (l == r) {
        segs[n] += v;
    } else {
        int m = (l+r)/2;
        if (l <= i && i <= m) {
            updates(2*n, l, m, i, v);
        } else {
            updates(2*n+1, m+1, r, i, v);
        }
        segs[n] = segs[2*n] + segs[2*n+1];
    }
}
void updatem(int n, int l, int r, int a, int b, int v) {
    lazypropagate(n, l, r);
    if (b < l || r < a) {
        return;
    } else if (a <= l && r <= b) {
        lazy[n] += v;
        lazypropagate(n, l, r);
    } else {
        int m = (l+r)/2;
        updatem(2*n, l, m, a, b, v);
        updatem(2*n+1, m+1, r, a, b, v);
        segmn[n] = min(segmn[2*n], segmn[2*n+1]);
        segmx[n] = max(segmx[2*n], segmx[2*n+1]);
    }
}
int querys(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return 0;
    } else if (a <= l && r <= b) {
        return segs[n];
    } else {
        int m = (l+r)/2;
        return querys(2*n, l, m, a, b) + querys(2*n+1, m+1, r, a, b);
    }
}
int querymn(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return INT_MAX;
    }
    lazypropagate(n, l, r); 
    if (a <= l && r <= b) {
        return segmn[n];
    } else {
        int m = (l+r)/2;
        return min(querymn(2*n, l, m, a, b), querymn(2*n+1, m+1, r, a, b));
    }
}
int querymx(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return INT_MIN;
    }
    lazypropagate(n, l, r); 
    if (a <= l && r <= b) {
        return segmx[n];
    } else {
        int m = (l+r)/2;
        return max(querymx(2*n, l, m, a, b), querymx(2*n+1, m+1, r, a, b));
    }
}
int trav(int q, int c, vector<int32_t> &v) {
    int l = 0, r = q-1;
    while(l < r) {
        int m = (l+r+1)/2;
        if (querymx(1, 0, q-1, m, q-1)-querymn(1, 0, q-1, m, q-1) >= c) {
            l = m;
        } else {
            r = m-1;
        }
    }
    if (querymx(1, 0, q-1, l, q-1)-querymn(1, 0, q-1, l, q-1) >= c) {
        int ans = l+1;
        for (int i = l+2; i < q; i++) {
            if ((v[l+1] < 0 && v[i] >= 0)||(v[l+1] >= 0 && v[i] < 0)) {
                break;
            }
            ans = i;
        }
        return ans;
    } else {
        return -1;
    }
}
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
    int n = c.size(), q = l.size();
    vector<int32_t> ans(q);
    for (int i = 0; i < q; i++) {
        updatem(1, 0, q-1, i, q-1, v[i]);
        updates(1, 0, q-1, i, v[i]);
    }
    //for (int i = 0; i < n; i++) {
    //    cout << querymn(1, 0, q-1, i, i) << " ";
    //}
    //cout << endl;
    //for (int i = 0; i < n; i++) {
    //    cout << i << " " << querymx(1, 0, q-1, i, q-1)-querymn(1, 0, q-1, i, q-1) << endl;
    //}
    for (int i = 0; i < n; i++) {
        int ind = trav(q, c[i], v);
        //cout << ind << endl;
        if (ind == -1) {
            ans[i] = segs[i];
            continue;
        }
        if (v[ind] < 0) {
            if (ind == q-1) {
                ans[i] = 0;
            } else {
                ans[i] = querys(1, 0, q-1, ind+1, q-1);
            }
        } else {
            if (ind == q-1) {
                ans[i] = c[i];
            } else {
                ans[i] = c[i]+querys(1, 0, q-1, ind+1, q-1);
            }
        }
        ans[i] = min(ans[i], c[i]);
        ans[i] = max(ans[i], 0);
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 12892 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Runtime error 6 ms 12892 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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