oj.uz

답안 #1070211

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1070211 2024-08-22T12:17:22 Z ArthuroWich 사탕 분배 (IOI21_candies) C++17
29 / 100
 1157 ms 35088 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 INT64_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 INT64_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) {
    int l = 0, r = q;
    while(l < r) {
        int m = (l+r+1)/2;
        if (querymx(1, 0, q, m, q)-querymn(1, 0, q, m, q) > c) {
            l = m;
        } else {
            r = m-1;
        }
    }
    if (querymx(1, 0, q, l, q)-querymn(1, 0, q, l, q) > c) {
        return l;
    } 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(n);
    for (int i = 1; i <= q; i++) {
        updatem(1, 0, q, i, q, v[i-1]);
        updates(1, 0, q, i, v[i-1]);
    }
    for (int i = 0; i < n; i++) {
        int ind = trav(q, c[i]);    
        if (ind == -1) {
            ans[i] = segs[1]-segmn[1];
            continue; 
        }
        if (segs[1] > querys(1, 0, q, 0, ind)) {
            ans[i] = c[i]-(querymx(1, 0, q, ind, q)-segs[1]);
        } else {
            ans[i] = segs[1]-querymn(1, 0, q, ind, q);
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6588 KB Output is correct
2 Correct 1 ms 6604 KB Output is correct
3 Correct 101 ms 30436 KB Output is correct
4 Correct 415 ms 10224 KB Output is correct
5 Correct 1133 ms 33596 KB Output is correct
6 Correct 1114 ms 34384 KB Output is correct
7 Correct 1108 ms 34924 KB Output is correct
8 Correct 1109 ms 33640 KB Output is correct
9 Correct 1157 ms 34896 KB Output is correct

Subtask #5
0 / 33.0

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