Submission #803931

#	Time	Username	Problem	Language	Result	Execution time	Memory
803931		physics07	Distributing Candies (IOI21_candies)	C++17	100 / 100	523 ms	24460 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=200002;
ll inf=1e18;
struct Node {
    ll m, M;
    Node operator+(const Node &p) {
        return {min(m, p.m), max(M, p.M)};
    }
};
struct seg{
    Node tree[4*MAX];
    ll lazy[4*MAX];
    void lazy_prop(int node, int s, int e) {
        tree[node].m+=lazy[node];
        tree[node].M+=lazy[node];
        if(s!=e) {
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
    void update(int node, int s, int e, int l, int r, int v) {
        lazy_prop(node, s, e);
        if(s>r || e<l) return;
        if(s>=l && e<=r) {
            lazy[node]+=v;
            lazy_prop(node, s, e);
            return;
        }
        int m=s+e>>1;
        update(node*2, s, m, l, r, v);
        update(node*2+1, m+1, e, l, r, v);
        tree[node]=tree[node*2]+tree[node*2+1];
    }
    int query(int node, int s, int e, ll c, ll m, ll M) {
        lazy_prop(node, s, e);
        if(s==e) {
            if(max(tree[node].M, M)-min(tree[node].m, m)>c) return s;
            return s-1;
        }
        int mid=s+e>>1;
        lazy_prop(node*2, s, mid);
        lazy_prop(node*2+1, mid+1, e);
        pair<ll, ll> curr={min(m, tree[node*2+1].m), max(M, tree[node*2+1].M)};
        if(curr.second-curr.first>c) return query(node*2+1, mid+1, e, c, m, M);
        else return query(node*2, s, mid, c, curr.first, curr.second);
    }
    ll get(int node, int s, int e, int idx) {
        lazy_prop(node, s, e);
        if(s>idx || e<idx) return -1e18;
        if(s==e) return tree[node].m;
        int m=s+e>>1;
        return max(get(node*2, s, m, idx), get(node*2+1, m+1, e, idx));
    }
    Node val(int node, int s, int e, int l, int r) {
        lazy_prop(node, s, e);
        if(s>r || e<l) return {inf, -inf};
        if(s>=l && e<=r) return tree[node];
        int m=s+e>>1;
        return val(node*2, s, m, l, r)+val(node*2+1, m+1, e, l, r);
    }
} tree;
struct query{
    int s, v, idx;
    bool operator<(const query &Q) const {
        return s<Q.s;
    }
};
vector<query> v;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> diff) {
    int n = c.size(), q=r.size();
    for(int i=0; i<q; i++) {
        v.push_back({l[i], diff[i], i+1});
        v.push_back({r[i]+1, -diff[i], i+1});
    }
    sort(v.begin(), v.end());
    vector<int> ans(n);
    int curr=0;
    for(int i=0; i<n; i++) {
        for(; curr<2*q; curr++) {
            if(v[curr].s==i) tree.update(1, 0, q, v[curr].idx, q, v[curr].v);
            else break;
        }
        int p=tree.query(1, 0, q, c[i], inf, -inf);
        ll ed=tree.get(1, 0, q, q);
        if(p==-1) {
            Node cnt=tree.val(1, 0, q, 0, q);
            ans[i]=ed-cnt.m;
            continue;
        }
        Node cnt=tree.val(1, 0, q, p, q);
        if(tree.get(1, 0, q, p)==cnt.m) ans[i]=c[i]-cnt.M+ed;
        else ans[i]=ed-cnt.m;
    }
    return ans;
}

Compilation message (stderr)

candies.cpp: In member function 'void seg::update(int, int, int, int, int, int)':
candies.cpp:33:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int m=s+e>>1;
      |               ~^~
candies.cpp: In member function 'int seg::query(int, int, int, ll, ll, ll)':
candies.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid=s+e>>1;
      |                 ~^~
candies.cpp: In member function 'll seg::get(int, int, int, int)':
candies.cpp:55:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int m=s+e>>1;
      |               ~^~
candies.cpp: In member function 'Node seg::val(int, int, int, int, int)':
candies.cpp:62:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int m=s+e>>1;
      |               ~^~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33