Submission #751530

#TimeUsernameProblemLanguageResultExecution timeMemory
751530JakobZorzSure Bet (CEOI17_sure)C++14
100 / 100
85 ms3684 KiB
#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <set> #include <stack> #include <limits.h> #include <math.h> #include <iomanip> #include <bitset> #include <unordered_map> #include <map> //#pragma GCC target("popcnt") #define ll long long using namespace std; const int MOD = 1e9 + 7; //#define SEGTREE //#define TREE //#define DSU #define MATH #ifdef SEGTREE template<class Type> class SegmentTree { Type (*func)(Type a, Type b); vector<Type> nodes; vector<int> l; vector<int> r; int size_log2; Type neutral; void init_node(int node) { if(node >= (1 << size_log2)) return; l[2 * node] = l[node]; r[2 * node] = (l[node] + r[node]) / 2; init_node(2 * node); l[2 * node + 1] = (l[node] + r[node]) / 2; r[2 * node + 1] = r[node]; init_node(2 * node + 1); nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]); } void update_node(int node) { if(node < (1 << size_log2)) nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]); if(node != 1) update_node(node / 2); } Type get(int node, int ll_, int rr) { if(rr <= l[node] || ll_ >= r[node]) return neutral; if(ll_ <= l[node] && rr >= r[node]) return nodes[node]; Type left = get(2 * node, ll_, rr); Type right = get(2 * node + 1, ll_, rr); return func(left, right); } public: SegmentTree(Type (*func)(Type a, Type b), vector<Type> vector, Type neutral) : func(func), neutral(neutral) { size_log2 = 0; while((1 << size_log2) < vector.size()) size_log2++; nodes.resize((1 << size_log2) * 2); l.resize((1 << size_log2) * 2); r.resize((1 << size_log2) * 2); for(int i = 0; i < vector.size(); i++) nodes[(1 << size_log2) + i] = vector[i]; l[1] = 0; r[1] = 1 << size_log2; init_node(1); } void set(int idx, Type el) { nodes[(1 << size_log2) + idx] = el; update_node((1 << size_log2) + idx); } Type get(int l, int r) { return get(1, l, r); } Type get(int idx) { return nodes[(1 << size_log2) + idx]; } Type get() { return nodes[1]; } int get_first_larger_or_eq_than(int bound) { return get_first_larger_or_eq_than(1, bound); } int get_first_larger_or_eq_than(int node, int bound) { if(node >= (1 << size_log2)) { return node - (1 << size_log2); } if(nodes[node * 2] > bound) return get_first_larger_or_eq_than(node * 2, bound); else return get_first_larger_or_eq_than(node * 2 + 1, bound - nodes[node * 2]); } }; #endif #ifdef TREE #define POW 18 struct Node { int parents[POW]; vector<int> conns; int depth; int value; int subtree_depth; int subtree_size; int euler; int val; int res; }; ll add(ll a, ll b) { return a + b; } Node nodes[200000]; int n; int setup(int node, int depth, int euler, ll dist) { dist += nodes[node].value; nodes[node].depth = depth; nodes[node].euler = euler++; for(int i = 1; i < POW; i++) { nodes[node].parents[i] = nodes[nodes[node].parents[i - 1]].parents[i - 1]; } int size = 1; for(int i = 0; i < nodes[node].conns.size(); i++) { int child = nodes[node].conns[i]; if(child != nodes[node].parents[0]) { nodes[child].parents[0] = node; euler = setup(child, depth + 1, euler, dist); size += nodes[child].subtree_size; } } nodes[node].subtree_size = size; return euler; } void setup_tree(int root) { nodes[root].parents[0] = root; setup(root, 0, 0, 0); } int get_subtree_depth(int node) { if(nodes[node].subtree_depth) return nodes[node].subtree_depth; int max_depth = 1; for(int child : nodes[node].conns) { if(child == nodes[node].parents[0]) continue; max_depth = max(max_depth, get_subtree_depth(child) + 1); } nodes[node].subtree_depth = max_depth; return max_depth; } int get_parent(int node, int depth) { if(depth > nodes[node].depth) return -1; int climber = node; for(int i = 0; i < POW; i++) { if(depth & (1 << i) && climber != -1) climber = nodes[climber].parents[i]; } return climber; } int lca(int a, int b) { if(nodes[a].depth < nodes[b].depth) swap(a, b); a = get_parent(a, nodes[a].depth - nodes[b].depth); if(a == b) return a; for(int i = POW - 1; i >= 0; i--) { if(nodes[a].parents[i] != nodes[b].parents[i]) { a = nodes[a].parents[i]; b = nodes[b].parents[i]; } } return nodes[a].parents[0]; } #endif #ifdef DSU class Dsu { vector<int> arr; int num_sets; public: Dsu(int size) { arr = vector<int>(size, -1); num_sets = size; } int merge(int a, int b) { a = get(a); b = get(b); if(a == b) return a; if(arr[a] > arr[b]) swap(a, b); arr[a] += arr[b]; arr[b] = a; num_sets--; return a; } int get(int a) { if(arr[a] < 0) return a; arr[a] = get(arr[a]); return get(arr[a]); } int get_size(int a) { return -arr[get(a)]; } int get_num_sets() { return num_sets; } }; #endif #ifdef MATH ll dpf[2000001]; ll factorial(ll n) { if(n == 0) return 1; if(dpf[n]) return dpf[n]; ll result = factorial(n - 1) * n; result %= MOD; dpf[n] = result; return result; } ll powm(ll base, ll exp) { ll result = 1; for(int i = 0; i < 64; i++) { if((exp >> i) % 2 == 1) { result *= base; result %= MOD; } base *= base; base %= MOD; } return result; } ll inverse(ll n) { return powm(n, MOD - 2); } ll dpif[2000001]; ll inverse_factorial(ll n) { if(dpif[n]) return dpif[n]; ll result = inverse(factorial(n)); dpif[n] = result; return result; } ll choose(ll n, ll k) { return (((factorial(n)*inverse_factorial(n-k))%MOD)*inverse_factorial(k))%MOD; } ll gcd(ll a, ll b){ if(a==b) return a; if(a<b) swap(a,b); if(b==0) return a; return gcd(b, a%b); } #endif int main(){ ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL); //freopen("mootube.in","r",stdin); //freopen("mootube.out","w",stdout); int n; cin>>n; vector<double>a1(n+1); vector<double>a2(n+1); for(int i=0;i<n;i++) cin>>a1[i]>>a2[i]; sort(a1.begin(),a1.end()); reverse(a1.begin(),a1.end()); sort(a2.begin(),a2.end()); reverse(a2.begin(),a2.end()); for(int i=1;i<=n;i++){ a1[i]+=a1[i-1]; a2[i]+=a2[i-1]; } double res=2; for(int i=0;i<=n;i++){ /*for(int j=0;j<=n;j++){ double c=min(a1[i],a2[j])-i-j; r=max(r,c); }*/ int l=0,r=n+1; while(l!=r-1){ int mid=(l+r)/2; if(min(a1[i],a2[mid])<min(a1[i],a2[mid+1])-1){ l=mid; }else{ r=mid; } } res=max(max(res,min(a1[i],a2[r])-r-i),max(res,min(a1[i],a2[l])-l-i)); //cout<<r<<endl; } printf("%.4lf\n",(double)(res-2)); return 0; } /* 4 1.4 3.7 1.2 2 1.6 1.4 1.9 1.5 4 3 3 3 3 3 3 1 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...