Submission #629776

#	Time	Username	Problem	Language	Result	Execution time	Memory
629776		Cross_Ratio	Distributing Candies (IOI21_candies)	C++17	100 / 100	1324 ms	48892 KiB

candies

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

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