oj.uz

Submission #1109839

# Submission time Handle Problem Language Result Execution time Memory
1109839 2024-11-07T17:59:10 Z cpptowin Measures (CEOI22_measures) C++17
100 / 100
 537 ms 41080 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)));
    }
    // cout << ss(nen);
    // en;
    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);
        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);
        // cout << val;en;
        // fo(i, 1, 4) cout << minn.get(i, i) << ' ';
        // en;
        // fo(i, 1, 4) cout << maxx.get(i, i) << ' ';
        // en;
        int u = maxx.get(1, lb);
        int v = minn.get(lb, ss(nen));
        maximize(ans, u - v);
        // cout << u << ' ' << v;
        // en;
        if(ans & 1) cout << ans / 2 << '.' << 5 << ' ';
        else cout << ans / 2 << ' ';
    }
}

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:287:13: warning: unused variable 'mi' [-Wunused-variable]
  287 |         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
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8784 KB Output is correct
2 Correct 4 ms 8784 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct
5 Correct 3 ms 8784 KB Output is correct
6 Correct 3 ms 8784 KB Output is correct
7 Correct 4 ms 8784 KB Output is correct
8 Correct 3 ms 8784 KB Output is correct
9 Correct 225 ms 39828 KB Output is correct
10 Correct 236 ms 39924 KB Output is correct
11 Correct 38 ms 14836 KB Output is correct
12 Correct 251 ms 39828 KB Output is correct
13 Correct 219 ms 39516 KB Output is correct
14 Correct 239 ms 39880 KB Output is correct
15 Correct 238 ms 39360 KB Output is correct
16 Correct 206 ms 39940 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 39096 KB Output is correct
2 Correct 368 ms 40640 KB Output is correct
3 Correct 63 ms 15808 KB Output is correct
4 Correct 356 ms 38592 KB Output is correct
5 Correct 391 ms 39872 KB Output is correct
6 Correct 341 ms 39104 KB Output is correct
7 Correct 368 ms 39900 KB Output is correct
8 Correct 387 ms 38628 KB Output is correct
9 Correct 358 ms 38848 KB Output is correct
10 Correct 340 ms 40960 KB Output is correct
11 Correct 374 ms 39344 KB Output is correct
12 Correct 360 ms 40428 KB Output is correct
13 Correct 374 ms 38528 KB Output is correct
14 Correct 374 ms 40592 KB Output is correct
15 Correct 378 ms 40600 KB Output is correct
16 Correct 373 ms 38600 KB Output is correct
17 Correct 370 ms 40016 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 39096 KB Output is correct
2 Correct 368 ms 40640 KB Output is correct
3 Correct 63 ms 15808 KB Output is correct
4 Correct 356 ms 38592 KB Output is correct
5 Correct 391 ms 39872 KB Output is correct
6 Correct 341 ms 39104 KB Output is correct
7 Correct 368 ms 39900 KB Output is correct
8 Correct 387 ms 38628 KB Output is correct
9 Correct 358 ms 38848 KB Output is correct
10 Correct 340 ms 40960 KB Output is correct
11 Correct 374 ms 39344 KB Output is correct
12 Correct 360 ms 40428 KB Output is correct
13 Correct 374 ms 38528 KB Output is correct
14 Correct 374 ms 40592 KB Output is correct
15 Correct 378 ms 40600 KB Output is correct
16 Correct 373 ms 38600 KB Output is correct
17 Correct 370 ms 40016 KB Output is correct
18 Correct 492 ms 39008 KB Output is correct
19 Correct 505 ms 40808 KB Output is correct
20 Correct 53 ms 15808 KB Output is correct
21 Correct 412 ms 38788 KB Output is correct
22 Correct 407 ms 39196 KB Output is correct
23 Correct 410 ms 38972 KB Output is correct
24 Correct 490 ms 39616 KB Output is correct
25 Correct 382 ms 38592 KB Output is correct
26 Correct 537 ms 38596 KB Output is correct
27 Correct 534 ms 41080 KB Output is correct
28 Correct 443 ms 39104 KB Output is correct
29 Correct 467 ms 40364 KB Output is correct
30 Correct 411 ms 38524 KB Output is correct
31 Correct 394 ms 40592 KB Output is correct
32 Correct 361 ms 40384 KB Output is correct
33 Correct 535 ms 38592 KB Output is correct
34 Correct 399 ms 39872 KB Output is correct