Submission #1017178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017178		caterpillow	Matching (CEOI11_mat)	C++17	0 / 100	852 ms	18972 KiB

mat

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

using db = long double;
const db inf = 1e9;
const db eps = 1e-12;
const db mxr = 1e9;

struct Line {
    db m, c;

    db operator()(db x) {
        return m * x + c;
    }
    db inter(const Line& b) const {
        return (c - b.c) / (b.m - m);
    }
};

using ptr = struct Node*;
struct Node {
    Line line;
    ptr l, r;
};

db query(ptr n, db x, db l = 0, db r = mxr) {
    if (!n) return inf;
    db m = (r + l) / 2;
    if (x <= m) return min(query(n->l, x, l, m), n->line(x));
    else return min(n->line(x), query(n->r, x, m, r));
};

ptr ins(ptr n, Line cur, db l = 0, db r = mxr) {
    if (r - l < eps) return 0;
    if (!n) return new Node {cur, 0, 0};
    db m = (l + r) / 2;
    if (cur(m) < n->line(m)) swap(cur, n->line);
    bool lhs = cur(l) < n->line(l);
    bool rhs = cur(r) < n->line(r);
    if (lhs) n->l = ins(n->l, cur, l, m);
    if (rhs) n->r = ins(n->r, cur, m, r);
    return n;
}


/*

cht

*/

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n; cin >> n;
    using pd = pair<db, db>;
    vt<pd> pts(n);
    F0R (i, n) cin >> pts[i].f >> pts[i].s;
    ptr tree = 0;
    for (auto [x, maxr] : pts) {
        db rtrad = min(sqrtl(maxr), query(tree, x));
        cout << rtrad * rtrad << endl;
        db fact = (db) 1.0 / (2 * rtrad);
        tree = ins(tree, {fact, - x * fact});
    }
}

Compilation message (stderr)

mat.cpp:92:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main() {
      | ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10