oj.uz

Submission #1109834

# Submission time Handle Problem Language Result Execution time Memory
1109834 2024-11-07T17:44:05 Z cpptowin Measures (CEOI22_measures) C++17
76 / 100
 529 ms 41156 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
#define UNIQUE(v) v.erase(unique(all(v)), v.end())
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if (x < 0)
        x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if (x < 0)
        x += mod;
}
struct SegmentTree
{
    vector<int> st, lazy;
    int n;
    /// real n
    SegmentTree(int _n = 0) : n(_n)
    {
        st.resize(4 * n + 10, inf);
        lazy.resize(4 * n + 10);
    }
    void resize(int _n)
    {
        n = _n;
        st.resize(4 * n + 10, inf);
        lazy.resize(4 * n + 10);
    }
    void down(int id, int l, int r)
    {
        st[id << 1] += lazy[id];
        lazy[id << 1] += lazy[id];
        st[id << 1 | 1] += lazy[id];
        lazy[id << 1 | 1] += lazy[id];
        lazy[id] = 0;
    }

    void update(int id, int l, int r, int u, int v, int val)
    {
        if (u > r || l > v)
            return;
        if (u <= l && r <= v)
        {
            st[id] += val;
            lazy[id] += val;
            return;
        }
        down(id, l, r);
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }

    void assign(int id, int l, int r, int x, int val)
    {
        if (l > x or r < x)
            return;
        if (l == r)
        {
            st[id] = val;
            lazy[id] = 0;
            return;
        }
        down(id, l, r);
        int mid = l + r >> 1;
        assign(id << 1, l, mid, x, val);
        assign(id << 1 | 1, mid + 1, r, x, val);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }
    int get(int id, int l, int r, int u, int v)
    {
        if (l > v || u > r)
            return inf;
        if (u <= l && r <= v)
            return st[id];
        down(id, l, r);
        int mid = (l + r) >> 1;
        return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
    int get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
    void update(int l, int r, int val)
    {
        update(1, 1, n, l, r, val);
    }
    void assign(int x, int val)
    {
        assign(1, 1, n, x, val);
    }
};
struct SegmentTree1
{
    vector<int> st, lazy;
    int n;
    /// real n
    SegmentTree1(int _n = 0) : n(_n)
    {
        st.resize(4 * n + 10, -inf);
        lazy.resize(4 * n + 10);
    }
    void resize(int _n)
    {
        n = _n;
        st.resize(4 * n + 10);
        lazy.resize(4 * n + 10);
    }
    void down(int id, int l, int r)
    {
        st[id << 1] += lazy[id];
        lazy[id << 1] += lazy[id];
        st[id << 1 | 1] += lazy[id];
        lazy[id << 1 | 1] += lazy[id];
        lazy[id] = 0;
    }

    void update(int id, int l, int r, int u, int v, int val)
    {
        if (u > r || l > v)
            return;
        if (u <= l && r <= v)
        {
            st[id] += val;
            lazy[id] += val;
            return;
        }
        down(id, l, r);
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    void assign(int id, int l, int r, int x, int val)
    {
        if (l > x or r < x)
            return;
        if (l == r)
        {
            st[id] = val;
            lazy[id] = 0;
            return;
        }
        down(id, l, r);
        int mid = l + r >> 1;
        assign(id << 1, l, mid, x, val);
        assign(id << 1 | 1, mid + 1, r, x, val);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    int get(int id, int l, int r, int u, int v)
    {
        if (l > v || u > r)
            return -inf;
        if (u <= l && r <= v)
            return st[id];
        down(id, l, r);
        int mid = (l + r) >> 1;
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
    int get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
    void update(int l, int r, int val)
    {
        update(1, 1, n, l, r, val);
    }
    void assign(int x, int val)
    {
        assign(1, 1, n, x, val);
    }
};
struct BIT
{
    int t[maxn];
    void up(int x, int val)
    {
        for (; x < maxn; x += lb(x))
            t[x] += val;
    }
    int get(int x)
    {
        int ans = 0;
        for (; x; x -= lb(x))
            ans += t[x];
        return ans;
    }
} t;
vi nen;
int n, q, d;
int qry[maxn], a[maxn];
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q >> d;
    fo(i, 1, n)
    {
        cin >> a[i];
        nen.pb(a[i]);
    }
    fo(i, 1, q)
    {
        cin >> qry[i];
        nen.pb(qry[i]);
    }
    sort(all(nen));
    UNIQUE(nen);
    SegmentTree minn(ss(nen));
    SegmentTree1 maxx(ss(nen));
    sort(a + 1, a + n + 1);
    int ans = 0;
    fo(i, 1, n)
    {
        int lb = lower_bound(all(nen), a[i]) - nen.begin() + 1;
        t.up(lb, 1);
        int val = a[i] - i * d;
        int val1 = minn.get(lb, lb);
        if (val1 > val)
            minn.assign(lb, val);
        val1 = maxx.get(lb, lb);
        if (val1 < val)
            maxx.assign(lb, val);
        maximize(ans, maxx.get(1, lb) - minn.get(lb,ss(nen)));
    }
    fo(i, 1, q)
    {
        int lb = lower_bound(all(nen), qry[i]) - nen.begin() + 1;
        minn.update(lb + 1, ss(nen), -d);
        maxx.update(lb + 1, ss(nen), -d);
        int mi = minn.get(lb + 1, ss(nen));
        t.up(lb, 1);
        int id = t.get(lb) + 1;
        int val = qry[i] - id * d;
        int val1 = minn.get(lb, lb);
        if (val1 > val)
            minn.assign(lb, val);
        val1 = maxx.get(lb, lb);
        if (val1 < val)
            maxx.assign(lb, val);
        int u = maxx.get(1,lb);
        int v = minn.get(lb,ss(nen));
        maximize(ans,u - v);
        if(ans & 1) cout << ans / 2 << '.' << 5 << ' ';
        else cout << ans / 2 << ' ';
        // cout << (double)0.5 * ans << ' ';
    }
}

Compilation message

Main.cpp: In member function 'void SegmentTree::assign(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:113:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void SegmentTree1::assign(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:193:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  193 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: At global scope:
Main.cpp:240:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  240 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:285:13: warning: unused variable 'mi' [-Wunused-variable]
  285 |         int mi = minn.get(lb + 1, ss(nen));
      |             ^~
Main.cpp:245:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  245 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:246:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  246 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8784 KB Output is correct
2 Incorrect 3 ms 8796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8784 KB Output is correct
2 Incorrect 3 ms 8796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 38896 KB Output is correct
2 Correct 372 ms 40672 KB Output is correct
3 Correct 56 ms 15808 KB Output is correct
4 Correct 358 ms 38536 KB Output is correct
5 Correct 434 ms 40032 KB Output is correct
6 Correct 385 ms 39116 KB Output is correct
7 Correct 379 ms 40112 KB Output is correct
8 Correct 356 ms 38592 KB Output is correct
9 Correct 354 ms 38592 KB Output is correct
10 Correct 345 ms 41152 KB Output is correct
11 Correct 363 ms 39360 KB Output is correct
12 Correct 291 ms 32972 KB Output is correct
13 Correct 306 ms 35212 KB Output is correct
14 Correct 292 ms 37072 KB Output is correct
15 Correct 285 ms 37068 KB Output is correct
16 Correct 353 ms 35268 KB Output is correct
17 Correct 369 ms 36544 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 38896 KB Output is correct
2 Correct 372 ms 40672 KB Output is correct
3 Correct 56 ms 15808 KB Output is correct
4 Correct 358 ms 38536 KB Output is correct
5 Correct 434 ms 40032 KB Output is correct
6 Correct 385 ms 39116 KB Output is correct
7 Correct 379 ms 40112 KB Output is correct
8 Correct 356 ms 38592 KB Output is correct
9 Correct 354 ms 38592 KB Output is correct
10 Correct 345 ms 41152 KB Output is correct
11 Correct 363 ms 39360 KB Output is correct
12 Correct 291 ms 32972 KB Output is correct
13 Correct 306 ms 35212 KB Output is correct
14 Correct 292 ms 37072 KB Output is correct
15 Correct 285 ms 37068 KB Output is correct
16 Correct 353 ms 35268 KB Output is correct
17 Correct 369 ms 36544 KB Output is correct
18 Correct 529 ms 39112 KB Output is correct
19 Correct 518 ms 40640 KB Output is correct
20 Correct 66 ms 15760 KB Output is correct
21 Correct 429 ms 38772 KB Output is correct
22 Correct 432 ms 39112 KB Output is correct
23 Correct 390 ms 38788 KB Output is correct
24 Correct 492 ms 39616 KB Output is correct
25 Correct 359 ms 38752 KB Output is correct
26 Correct 488 ms 38592 KB Output is correct
27 Correct 473 ms 41156 KB Output is correct
28 Correct 428 ms 39104 KB Output is correct
29 Correct 463 ms 40380 KB Output is correct
30 Correct 397 ms 38592 KB Output is correct
31 Correct 404 ms 40548 KB Output is correct
32 Correct 364 ms 40384 KB Output is correct
33 Correct 508 ms 38748 KB Output is correct
34 Correct 412 ms 39872 KB Output is correct