oj.uz

Submission #632106

# Submission time Handle Problem Language Result Execution time Memory
632106 2022-08-19T12:36:51 Z arayi Measures (CEOI22_measures) C++17
100 / 100
 631 ms 35056 KB 
// Arayi
#include <bits/stdc++.h>
#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int>
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;

lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x, ld y1, ld x2, ld y2)
{
    return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
    return (a * (a + 1LL)) / 2;
}
mt19937 rnd(363542);
char vow[] = {'a', 'e', 'i', 'o', 'u'};
int dx[] = {0, -1, 0, 1, -1, -1, 1, 1, 0};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1, 0};
char dc[] = {'R', 'D', 'L', 'U'};

const int N = 5e5 + 20;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const ld e = 1e-13;
const int T = 128;

lli bp(lli a, lli b = mod - 2LL)
{
    lli ret = 1;
    while (b)
    {
        if (b & 1)
            ret *= a, ret %= mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ret;
}
ostream &operator<<(ostream &c, pir a)
{
    c << a.fr << " " << a.sc;
    return c;
}
template <class T>
void maxi(T &a, T b)
{
    a = max(a, b);
}
template <class T>
void mini(T &a, T b)
{
    a = min(a, b);
}

int n, m;
lli x[N];
lli sum, d;
lli fl[4 * N], t[4 * N], t1[4 * N];
void push(int nd)
{
    fl[nd * 2] += fl[nd];
    fl[nd * 2 + 1] += fl[nd];
    t[nd] += fl[nd];
    t1[nd] += fl[nd];
    fl[nd] = 0;
}
void upd(int l, int r, lli v, int nl = 0, int nr = n + m + 1, int nd = 1)
{
    push(nd);
    if (l > nr || r < nl)
        return;
    if (l == nl && r == nr)
    {
        fl[nd] += v;
        push(nd);
        return;
    }
    int md = (nl + nr) / 2;
    upd(l, min(md, r), v, nl, md, nd * 2);
    upd(max(md + 1, l), r, v, md + 1, nr, nd * 2 + 1);
    t[nd] = min(t[nd * 2], t[nd * 2 + 1]);
    t1[nd] = max(t1[nd * 2], t1[nd * 2 + 1]);
}
lli qry(int l, int r, bool b, int nl = 0, int nr = n + m + 1, int nd = 1)
{
    push(nd);
    if (l > nr || r < nl)
    {
        if (b)
            return LLONG_MAX;
        else
            return LLONG_MIN;
    }
    if (l == nl && r == nr)
    {
        if (b)
            return t[nd];
        return t1[nd];
    }
    int md = (nl + nr) / 2;
    if (b)
        return min(qry(l, min(md, r), b, nl, md, nd * 2), qry(max(md + 1, l), r, b, md + 1, nr, nd * 2 + 1));
    return max(qry(l, min(md, r), b, nl, md, nd * 2), qry(max(md + 1, l), r, b, md + 1, nr, nd * 2 + 1));
}
int main()
{
    fastio;
    //freopen("input.in", "r", stdin);
    cin >> n >> m >> d;
    vector<pair<lli, int>> fp;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i];
        fp.ad(MP(x[i], i));
    }
    for (int i = n + 1; i <= n + m; i++)
    {
        cin >> x[i];
        fp.ad(MP(x[i], i));
    }
    sort(all(fp));
    set<int> st;
    for (int i = 1; i <= n; i++)
    {
        int i1 = upper_bound(all(fp), MP(x[i], i)) - fp.begin() - 1;
        auto p = st.upper_bound(i1);
        // cout << i1 << "-";
        if (p != st.end() && p != st.begin())
        {
            int hj = *p;
            int nx = *(--p);
            upd(i1 + 1, n + m + 1, d - (fp[hj].fr - x[i]));
            upd(nx + 1, n + m + 1, d - (x[i] - fp[nx].fr));
            upd(nx + 1, n + m + 1, -d + fp[hj].fr - fp[nx].fr);
            // cout << nx << " " << fp[nx].fr << endl;
            // cout << hj << " " << fp[hj].fr << endl;
        }
        else if (p != st.end())
        {
            int hj = *p;
            upd(i1 + 1, n + m + 1, d - (fp[hj].fr - x[i]));
            // cout << hj << " " << fp[hj].fr << endl;
        }
        else if (p != st.begin())
        {
            int nx = *(--p);
            upd(nx + 1, n + m + 1, d - (x[i] - fp[nx].fr));
            // cout << nx << " " << fp[nx].fr << endl;
        }
        maxi(sum, qry(i1, n + m + 1, 0) - qry(0, i1, 1));
        st.insert(i1);
        // cout << endl;
    }
    // cout << qry(0, 0, 0) << " " << qry(1, 1, 0) << " " << qry(2, 2, 0) << " " << qry(3, 3, 0) << " " << qry(4, 4, 0) << endl;
    for (int i = n + 1; i <= n + m; i++)
    {
        int i1 = upper_bound(all(fp), MP(x[i], i)) - fp.begin() - 1;
        auto p = st.upper_bound(i1);
        // cout << i1 << "-";
        if (p != st.end() && p != st.begin())
        {
            int hj = *p;
            int nx = *(--p);
            upd(i1 + 1, n + m + 1, d - (fp[hj].fr - x[i]));
            upd(nx + 1, n + m + 1, d - (x[i] - fp[nx].fr));
            upd(nx + 1, n + m + 1, -d + fp[hj].fr - fp[nx].fr);
            // cout << nx << " " << fp[nx].fr << endl;
            // cout << hj << " " << fp[hj].fr << endl;
        }
        else if (p != st.end())
        {
            int hj = *p;
            upd(i1 + 1, n + m + 1, d - (fp[hj].fr - x[i]));
            // cout << hj << " " << fp[hj].fr << endl;
        }
        else if (p != st.begin())
        {
            int nx = *(--p);
            upd(nx + 1, n + m + 1, d - (x[i] - fp[nx].fr));
            // cout << nx << " " << fp[nx].fr << endl;
        }
        maxi(sum, qry(i1, n + m + 1, 0) - qry(0, i1, 1));
        st.insert(i1);
        if (sum % 2LL == 0)
            cout << sum / 2LL << " ";
        else
            cout << sum / 2LL << ".5 ";
    }
    // cout << qry(0, 0, 0) << " " << qry(1, 1, 0) << " " << qry(2, 2, 0) << " " << qry(3, 3, 0) << " " << qry(4, 4, 0) << endl;
    cout << endl;
    return 0;
}

/*
    __
  *(><)*
    \/ /
    ||/
  --||
    ||
    /\
   /  \
  /    \

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 3 ms 636 KB Output is correct
8 Correct 2 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 3 ms 636 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 573 ms 31712 KB Output is correct
10 Correct 538 ms 31440 KB Output is correct
11 Correct 250 ms 31016 KB Output is correct
12 Correct 365 ms 31964 KB Output is correct
13 Correct 238 ms 31412 KB Output is correct
14 Correct 357 ms 31372 KB Output is correct
15 Correct 581 ms 31480 KB Output is correct
16 Correct 252 ms 31036 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 32568 KB Output is correct
2 Correct 265 ms 34704 KB Output is correct
3 Correct 264 ms 34688 KB Output is correct
4 Correct 255 ms 31988 KB Output is correct
5 Correct 257 ms 33784 KB Output is correct
6 Correct 259 ms 32920 KB Output is correct
7 Correct 259 ms 34368 KB Output is correct
8 Correct 258 ms 33336 KB Output is correct
9 Correct 254 ms 32712 KB Output is correct
10 Correct 272 ms 34860 KB Output is correct
11 Correct 259 ms 33476 KB Output is correct
12 Correct 266 ms 34636 KB Output is correct
13 Correct 254 ms 32312 KB Output is correct
14 Correct 260 ms 34748 KB Output is correct
15 Correct 265 ms 33504 KB Output is correct
16 Correct 252 ms 32764 KB Output is correct
17 Correct 262 ms 34124 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 32568 KB Output is correct
2 Correct 265 ms 34704 KB Output is correct
3 Correct 264 ms 34688 KB Output is correct
4 Correct 255 ms 31988 KB Output is correct
5 Correct 257 ms 33784 KB Output is correct
6 Correct 259 ms 32920 KB Output is correct
7 Correct 259 ms 34368 KB Output is correct
8 Correct 258 ms 33336 KB Output is correct
9 Correct 254 ms 32712 KB Output is correct
10 Correct 272 ms 34860 KB Output is correct
11 Correct 259 ms 33476 KB Output is correct
12 Correct 266 ms 34636 KB Output is correct
13 Correct 254 ms 32312 KB Output is correct
14 Correct 260 ms 34748 KB Output is correct
15 Correct 265 ms 33504 KB Output is correct
16 Correct 252 ms 32764 KB Output is correct
17 Correct 262 ms 34124 KB Output is correct
18 Correct 609 ms 32348 KB Output is correct
19 Correct 631 ms 34652 KB Output is correct
20 Correct 264 ms 34872 KB Output is correct
21 Correct 386 ms 33464 KB Output is correct
22 Correct 435 ms 33328 KB Output is correct
23 Correct 377 ms 33028 KB Output is correct
24 Correct 596 ms 33532 KB Output is correct
25 Correct 263 ms 33112 KB Output is correct
26 Correct 598 ms 32920 KB Output is correct
27 Correct 601 ms 35056 KB Output is correct
28 Correct 452 ms 32744 KB Output is correct
29 Correct 515 ms 33488 KB Output is correct
30 Correct 384 ms 31700 KB Output is correct
31 Correct 389 ms 34488 KB Output is correct
32 Correct 372 ms 33576 KB Output is correct
33 Correct 625 ms 31772 KB Output is correct
34 Correct 386 ms 33200 KB Output is correct