oj.uz

Submission #1073650

# Submission time Handle Problem Language Result Execution time Memory
1073650 2024-08-24T17:09:03 Z Wansur Distributing Candies (IOI21_candies) C++17
29 / 100
 654 ms 35180 KB 
#include <bits/stdc++.h>
#include "candies.h"

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 12;

ll p[maxn * 4], t[maxn * 4];
ll tp[maxn * 4], add[maxn * 4];
ll a[maxn], pref[maxn];
ll c[maxn];
int n, m;

void push(int v, int tl, int tr){
    if(tl == tr) return;
    int mid = tl + tr >> 1;
    if(p[v] != 0){
        p[v*2] = p[v];
        p[v*2+1] = p[v];
        add[v*2] = add[v];
        add[v*2+1] = add[v];
        t[v*2] = t[v*2+1] = 0;
        if(p[v] == 2){
            t[v*2] = pref[mid] - pref[tl-1];
            t[v*2+1] = pref[tr] - pref[mid];
        }
        t[v*2] += (mid - tl + 1) * add[v];
        t[v*2+1] += (tr - mid) * add[v];
    }
    else{
        t[v*2] += add[v] * (mid - tl + 1);
        t[v*2+1] += add[v] * (tr - mid);
        add[v*2] += add[v];
        add[v*2+1] += add[v];
    }
    p[v] = 0, add[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, int x){
    push(v, tl, tr);
    if(tl > r || l > tr) return;
    if(tl >= l && tr <= r){
        p[v] = x;
        add[v] = 0;
        if(x == 2) t[v] = pref[tr] - pref[tl - 1];
        else t[v] = 0;
        return;
    }
    int mid = tl + tr >> 1;
    upd(v*2, tl, mid, l, r, x);
    upd(v*2+1, mid+1, tr, l, r, x);
    t[v] = t[v*2] + t[v*2+1];
}

int get(int v, int tl, int tr, int pos){
    push(v, tl, tr);
    if(tl == tr){
        return t[v];
    }
    int mid = tl + tr >> 1;
    if(pos <= mid){
        return get(v*2, tl, mid, pos);
    }
    return get(v*2+1, mid+1, tr, pos);
}

void upd(int x){
    t[1] += x * n;
    add[1] += x;
    int pos = 0;
    for(int l = 1, r = n; l <= r;){
        int mid = l + r >> 1;
        int x = get(1, 1, n, mid);
        if(x < 0 || x > c[mid]){
            pos = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    if(pos == 0) return;
    if(x < 0) upd(1, 1, n, 1, pos, 1);
    else upd(1, 1, n, 1, pos, 2);
}

vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v){
    n = C.size(), m = l.size();
    vector<int> p(n), ans(n);
    for(int i=1;i<=n;i++){
        c[i] = C[i-1];
        p[i-1] = i;
    }
    sort(p.begin(), p.end(), [](int i, int j){
        return c[i] < c[j];
    });
    sort(c + 1, c + n + 1);
    for(int i=1;i<=n;i++){
        pref[i] = pref[i-1] + c[i];
    }
    for(int i=0;i<m;i++){
        upd(v[i]);
    }
    for(int i=0;i<n;i++){
        ans[p[i] - 1] = get(1, 1, n, i+1);
    }
    return ans;
}

Compilation message

candies.cpp: In function 'void push(int, int, int)':
candies.cpp:16:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
candies.cpp: In function 'void upd(int, int, int, int, int, int)':
candies.cpp:49:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
candies.cpp: In function 'int get(int, int, int, int)':
candies.cpp:60:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
candies.cpp: In function 'void upd(int)':
candies.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 0 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 484 ms 30160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 203 ms 9356 KB Output is correct
4 Correct 99 ms 25532 KB Output is correct
5 Correct 632 ms 30292 KB Output is correct
6 Correct 648 ms 34384 KB Output is correct
7 Correct 654 ms 35180 KB Output is correct
8 Correct 628 ms 33656 KB Output is correct
9 Correct 469 ms 35056 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 0 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -