Submission #1073650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073650		Wansur	Distributing Candies (IOI21_candies)	C++17	29 / 100	654 ms	35180 KiB

candies

#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 (stderr)

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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33