oj.uz

Submission #629776

# Submission time Handle Problem Language Result Execution time Memory
629776 2022-08-15T05:52:18 Z Cross_Ratio Distributing Candies (IOI21_candies) C++17
100 / 100
 1324 ms 48892 KB 
#include "candies.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
int C[200005];
int L[200005];
int R[200005];
int V[200005];
long long int B[200005];
int N, Q;
long long int D[200005];
typedef pair<long long int,long long int> P;
int sum(int a, int b) {
    if(a>=b) return 0;
    return B[b-1] - (a ? B[a-1] : 0);
}
const long long int INF = 1e18;
struct Node {
    long long int mi, ma;
    long long int p;
    int mid, mad;
    Node(long long int _i,long long int _a, long long int _p) : mi(_i), ma(_a), p(_p),mid(0),mad(0) {}
    Node() : mi(INF),ma(-INF),p(0),mid(0),mad(0) {}
};
struct SegTree {
    vector<Node> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
        for(i=0;i<MAX;i++) {
            seg[i].ma = 0;
            seg[i].mi = 0;
            seg[i].p = 0;
            seg[i].mad = seg[i].mid = 0;
        }
        for(i=MAX/2;i<MAX;i++) seg[i].mad = seg[i].mid = i - MAX/2;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i] = f(seg[2*i],seg[2*i+1]);
        }
    }
    void prop(int n, int ns, int ne) {
        if(!seg[n].p) return;
        seg[n].ma += seg[n].p;
        seg[n].mi += seg[n].p;
        if(n<MAX/2) {
            seg[2*n].p += seg[n].p;
            seg[2*n+1].p += seg[n].p;
        }
        seg[n].p = 0;
    }
    Node f(Node x, Node y) {
        Node c;
        c.p = 0;
        if(x.ma>y.ma) {
            c.ma = x.ma;
            c.mad = x.mad;
        }
        else if(x.ma<y.ma){
            c.ma = y.ma;
            c.mad = y.mad;
        }
        else {
            c.ma = x.ma;
            c.mad = max(x.mad, y.mad);
        }
        if(x.mi>y.mi) {
            c.mi = y.mi;
            c.mid = y.mid;
        }
        else if(x.mi<y.mi) {
            c.mi = x.mi;
            c.mid = x.mid;
        }
        else {
            c.mi = x.mi;
            c.mid = max(x.mid, y.mid);
        }
        return c;
    }
    void add(int s, int e, int k, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n].p += k;
            prop(n,ns,ne);
            return;
        }
        int mid = (ns + ne)/2;
        add(s,e,k,2*n,ns,mid);
        add(s,e,k,2*n+1,mid,ne);
        if(n<MAX/2) {
            seg[n] = f(seg[2*n],seg[2*n+1]);
        }
    }
    void add(int s, int e, int k) {
        add(s,e,k,1,0,MAX/2);
    }
    Node sum(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return Node();
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return f(sum(s,e,2*n,ns,mid),sum(s,e,2*n+1,mid,ne));
    }
    Node sum(int s, int e) {
        return sum(s,e,1,0,MAX/2);
    }
    int find_pos(int l, int r, long long int C) {
        if(l+1==r) return l;
        int mid = l + r >> 1;
        Node k = sum(mid, MAX/2, 1, 0, MAX/2);
        if(k.ma - k.mi >= C) return find_pos(mid, r, C);
        else return find_pos(l, mid, C);
    }
};
vector<int> distribute_candies(vector<int> _C, vector<int> _L,
                                    vector<int> _R, vector<int> _V) {
    N = _C.size();
    Q = _L.size();
    register int i, j;
    for(i=0;i<N;i++) C[i] = _C[i];
    for(i=0;i<Q;i++) {
        L[i] = _L[i];
        R[i] = _R[i];
        V[i] = _V[i];
        R[i]++;
    }
    SegTree tree(Q+5);
    tree.cons();
    vector<vector<P>> Query;
    Query.resize(N+1);
    for(i=0;i<Q;i++) {
        Query[L[i]].push_back(P(i,V[i]));
        Query[R[i]].push_back(P(i,-V[i]));
    }
    vector<int> ans;
    ans.resize(N);
    for(i=0;i<N;i++) {
        for(P k : Query[i]) {
            tree.add(0, k.first + 1, k.second);
        }
        int pos = tree.find_pos(0, Q, C[i]);
        Node k = tree.sum(pos, Q+1);
        long long int pval = tree.sum(pos, pos+1).mi;
        long long int mas = pval - k.mi;
        long long int mis = pval - k.ma;
        if(mas>=C[i]) {
            ans[i] = C[i] + tree.sum(k.mid,k.mid+1).mi;
        }
        else if(mis<=-C[i]) {
            ans[i] = tree.sum(k.mad,k.mad+1).mi;
        }
        else {
            ans[i] = tree.sum(k.mad,k.mad+1).mi;
        }
    }
    return ans;
}

Compilation message

candies.cpp: In member function 'Node SegTree::sum(int, int, int, int, int)':
candies.cpp:109:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
candies.cpp: In member function 'int SegTree::find_pos(int, int, long long int)':
candies.cpp:117:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |         int mid = l + r >> 1;
      |                   ~~^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:127:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  127 |     register int i, j;
      |                  ^
candies.cpp:127:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  127 |     register int i, j;
      |                     ^
candies.cpp:127:21: warning: unused variable 'j' [-Wunused-variable]

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 7 ms 764 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 46916 KB Output is correct
2 Correct 1324 ms 46152 KB Output is correct
3 Correct 1275 ms 45976 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 269 ms 35720 KB Output is correct
3 Correct 351 ms 10700 KB Output is correct
4 Correct 1250 ms 48024 KB Output is correct
5 Correct 1259 ms 48396 KB Output is correct
6 Correct 1121 ms 48892 KB Output is correct
7 Correct 1095 ms 48184 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 112 ms 32960 KB Output is correct
4 Correct 318 ms 9664 KB Output is correct
5 Correct 875 ms 41368 KB Output is correct
6 Correct 891 ms 42132 KB Output is correct
7 Correct 844 ms 42724 KB Output is correct
8 Correct 886 ms 41352 KB Output is correct
9 Correct 791 ms 42768 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 7 ms 764 KB Output is correct
6 Correct 1294 ms 46916 KB Output is correct
7 Correct 1324 ms 46152 KB Output is correct
8 Correct 1275 ms 45976 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 269 ms 35720 KB Output is correct
11 Correct 351 ms 10700 KB Output is correct
12 Correct 1250 ms 48024 KB Output is correct
13 Correct 1259 ms 48396 KB Output is correct
14 Correct 1121 ms 48892 KB Output is correct
15 Correct 1095 ms 48184 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 112 ms 32960 KB Output is correct
19 Correct 318 ms 9664 KB Output is correct
20 Correct 875 ms 41368 KB Output is correct
21 Correct 891 ms 42132 KB Output is correct
22 Correct 844 ms 42724 KB Output is correct
23 Correct 886 ms 41352 KB Output is correct
24 Correct 791 ms 42768 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 336 ms 9692 KB Output is correct
27 Correct 255 ms 35304 KB Output is correct
28 Correct 1303 ms 46560 KB Output is correct
29 Correct 1234 ms 47072 KB Output is correct
30 Correct 1230 ms 47196 KB Output is correct
31 Correct 1172 ms 47400 KB Output is correct
32 Correct 1141 ms 47600 KB Output is correct