oj.uz

Submission #803931

# Submission time Handle Problem Language Result Execution time Memory
803931 2023-08-03T06:36:14 Z physics07 Distributing Candies (IOI21_candies) C++17
100 / 100
 523 ms 24460 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 24388 KB Output is correct
2 Correct 493 ms 24396 KB Output is correct
3 Correct 368 ms 24392 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 293 ms 22180 KB Output is correct
3 Correct 115 ms 4016 KB Output is correct
4 Correct 390 ms 24400 KB Output is correct
5 Correct 469 ms 24396 KB Output is correct
6 Correct 523 ms 24400 KB Output is correct
7 Correct 496 ms 24276 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 150 ms 22180 KB Output is correct
4 Correct 93 ms 3000 KB Output is correct
5 Correct 269 ms 24280 KB Output is correct
6 Correct 293 ms 24456 KB Output is correct
7 Correct 320 ms 24396 KB Output is correct
8 Correct 245 ms 24392 KB Output is correct
9 Correct 293 ms 24428 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 441 ms 24388 KB Output is correct
7 Correct 493 ms 24396 KB Output is correct
8 Correct 368 ms 24392 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 293 ms 22180 KB Output is correct
11 Correct 115 ms 4016 KB Output is correct
12 Correct 390 ms 24400 KB Output is correct
13 Correct 469 ms 24396 KB Output is correct
14 Correct 523 ms 24400 KB Output is correct
15 Correct 496 ms 24276 KB Output is correct
16 Correct 1 ms 260 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 150 ms 22180 KB Output is correct
19 Correct 93 ms 3000 KB Output is correct
20 Correct 269 ms 24280 KB Output is correct
21 Correct 293 ms 24456 KB Output is correct
22 Correct 320 ms 24396 KB Output is correct
23 Correct 245 ms 24392 KB Output is correct
24 Correct 293 ms 24428 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 96 ms 2924 KB Output is correct
27 Correct 226 ms 22180 KB Output is correct
28 Correct 456 ms 24460 KB Output is correct
29 Correct 475 ms 24392 KB Output is correct
30 Correct 385 ms 24392 KB Output is correct
31 Correct 391 ms 24392 KB Output is correct
32 Correct 458 ms 24348 KB Output is correct