oj.uz

답안 #441549

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441549 2021-07-05T11:06:02 Z SorahISA 사탕 분배 (IOI21_candies) C++17
29 / 100
 1246 ms 21000 KB 
#include "candies.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1 << 18;
const int maxc = 1E9 + 5;

struct SegmentTree {
    int tag, val, last_change; /// tag is for range modify, val has no use if is not leaf
    char last_type;
    
    SegmentTree() {tag = 1, last_change = 0, last_type = 'E';}
};

SegmentTree seg[maxn*2];
vector<int> C, V, pre_V;

void PushTag(int idx) {
    if (seg[idx].tag == 1) return;
    seg[idx<<1].tag = seg[idx<<1|1].tag = seg[idx].tag;
    if (seg[idx].tag ==  0) seg[idx<<1].last_type = seg[idx<<1|1].last_type = 'E';
    if (seg[idx].tag == -1) seg[idx<<1].last_type = seg[idx<<1|1].last_type = 'F';
    seg[idx<<1].last_change = seg[idx<<1|1].last_change = seg[idx].last_change;
    seg[idx].tag = 1;
}

void Pull(int idx) {
    /// no need (?) ///
    return;
}

int CheckVal(int idx, int qID) {
    deque<int> stk;
    int goal = idx + maxn;
    while (goal > 1) stk.eb(goal >>= 1);
    while (!stk.empty()) PushTag(stk.back()), stk.pb();
    goal = idx + maxn;
    /// pre_V[qID+1] - pre_V[last_change] ///
    // cout << seg[goal].last_type << " " << seg[goal].last_change << ": ";
    if (seg[goal].last_type == 'E') return pre_V[qID] - pre_V[seg[goal].last_change];
    if (seg[goal].last_type == 'F') return pre_V[qID] - pre_V[seg[goal].last_change] + C[idx];
}

void PointModify(int qX, int val, int now = 1, int nL = 0, int nR = maxn-1) {
    if (nL == nR) return seg[now].val = val, void();
    PushTag(now);
    int nM = nL + nR >> 1;
    if (qX <= nM) PointModify(qX, val, now<<1,   nL,   nM);
    else          PointModify(qX, val, now<<1|1, nM+1, nR);
}

void RangeModify(int qL, int qR, int val, int qID, int now = 1, int nL = 0, int nR = maxn-1) {
    if (qL <= nL and nR <= qR) {
        seg[now].tag = seg[now].val = val;
        seg[now].last_change = qID;
        seg[now].last_type = val == 0 ? 'E' : 'F';
        return;
    }
    if (qR < nL or nR < qL) return;
    PushTag(now);
    int nM = nL + nR >> 1;
    RangeModify(qL, qR, val, qID, now<<1,   nL,   nM);
    RangeModify(qL, qR, val, qID, now<<1|1, nM+1, nR);
}

} /// end of namespace

vector<int> distribute_candies(vector<int> _C, vector<int> L, vector<int> R, vector<int> _V) {
    C.eb(0), C.eb(maxc), V.eb(0);
    int N = _C.size(), Q = _V.size();
    vector<pii> idx_C;
    for (int i = 0; i < N; ++i) C.eb(_C[i]), idx_C.eb(_C[i], i);
    for (auto &x : _V) V.eb(x);
    pre_V.assign(Q+1, 0), partial_sum(ALL(V), begin(pre_V));
    sort(ALL(C)), sort(ALL(idx_C));
    
    for (int i = 1; i <= Q; ++i) {
        // cout << "\n======\n";
        // for (int j = 0; j <= N; ++j) cout << CheckVal(j, i-1) << "\n";
        // cout << "======\n";
        int lo = 0, hi = N, mi;
        if (V[i] > 0) {
            /// nothing or full ///
            if (CheckVal(N, i-1) + V[i] >= C[N]) {
                RangeModify(0, N, -1, i); continue;
            }
            while (lo < hi) {
                mi = lo + hi >> 1;
                if (CheckVal(mi, i-1) + V[i] >= C[mi]) lo = mi + 1; /// [0, mi] is full
                else hi = mi;                                       /// [mi, N] is not full
            }
            /// [0, lo) is full ///
            PointModify(lo, CheckVal(lo, i-1) - CheckVal(lo-1, i-1));
            RangeModify(0, lo-1, -1, i);
        }
        else {
            /// nothing or empty ///
            if (CheckVal(N, i-1) + V[i] <= 0) {
                RangeModify(0, N, 0, i); continue;
            }
            while (lo < hi) {
                mi = lo + hi >> 1;
                if (CheckVal(mi, i-1) + V[i] <= 0) lo = mi + 1; /// [0, mi] is empty
                else hi = mi;                                   /// [mi, N] is not empty
            }
            /// [0, lo) is empty ///
            PointModify(lo, CheckVal(lo, i-1) - CheckVal(lo-1, i-1));
            RangeModify(0, lo-1, 0, i);
        }
        // cout << "\nbinary search gets " << lo << "\n";
    }
    
    // cout << "\n";
    
    vector<int> ans(N);
    for (int i = 1; i <= N; ++i) {
        int tmp_val = CheckVal(i, Q); // cout << tmp_val << "\n";
        ans[idx_C[i-1].Y] = tmp_val;
    }
    return ans;
}

Compilation message

candies.cpp: In function 'void {anonymous}::PointModify(int, int, int, int, int)':
candies.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     int nM = nL + nR >> 1;
      |              ~~~^~~~
candies.cpp: In function 'void {anonymous}::RangeModify(int, int, int, int, int, int, int)':
candies.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int nM = nL + nR >> 1;
      |              ~~~^~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:109:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |                 mi = lo + hi >> 1;
      |                      ~~~^~~~
candies.cpp:123:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |                 mi = lo + hi >> 1;
      |                      ~~~^~~~
candies.cpp: In function 'int {anonymous}::CheckVal(int, int)':
candies.cpp:54:16: warning: control reaches end of non-void function [-Wreturn-type]
   54 |     deque<int> stk;
      |                ^~~
candies.cpp: At global scope:
candies.cpp:48:6: warning: 'void {anonymous}::Pull(int)' defined but not used [-Wunused-function]
   48 | void Pull(int idx) {
      |      ^~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8396 KB Output is correct
2 Correct 6 ms 8524 KB Output is correct
3 Correct 638 ms 14956 KB Output is correct
4 Correct 146 ms 13152 KB Output is correct
5 Correct 1143 ms 19760 KB Output is correct
6 Correct 1167 ms 21000 KB Output is correct
7 Correct 1153 ms 21000 KB Output is correct
8 Correct 1246 ms 21000 KB Output is correct
9 Correct 966 ms 21000 KB Output is correct

Subtask #5
0 / 33.0

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