oj.uz

Submission #1109840

# Submission time Handle Problem Language Result Execution time Memory
1109840 2024-11-07T17:59:40 Z cpptowin Measures (CEOI22_measures) C++17
100 / 100
 555 ms 41228 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);
        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 << ' ';
    }
}

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
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 4 ms 8980 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 4 ms 8784 KB Output is correct
5 Correct 3 ms 8980 KB Output is correct
6 Correct 4 ms 8784 KB Output is correct
7 Correct 3 ms 8784 KB Output is correct
8 Correct 4 ms 8784 KB Output is correct
9 Correct 235 ms 38080 KB Output is correct
10 Correct 238 ms 38080 KB Output is correct
11 Correct 36 ms 13000 KB Output is correct
12 Correct 234 ms 38080 KB Output is correct
13 Correct 218 ms 38080 KB Output is correct
14 Correct 214 ms 38088 KB Output is correct
15 Correct 228 ms 37904 KB Output is correct
16 Correct 210 ms 38080 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 39028 KB Output is correct
2 Correct 361 ms 40640 KB Output is correct
3 Correct 51 ms 15604 KB Output is correct
4 Correct 363 ms 38768 KB Output is correct
5 Correct 345 ms 39800 KB Output is correct
6 Correct 365 ms 38884 KB Output is correct
7 Correct 369 ms 39912 KB Output is correct
8 Correct 379 ms 38664 KB Output is correct
9 Correct 367 ms 38592 KB Output is correct
10 Correct 364 ms 41160 KB Output is correct
11 Correct 386 ms 39484 KB Output is correct
12 Correct 377 ms 40332 KB Output is correct
13 Correct 364 ms 38592 KB Output is correct
14 Correct 359 ms 40640 KB Output is correct
15 Correct 358 ms 40384 KB Output is correct
16 Correct 357 ms 38684 KB Output is correct
17 Correct 362 ms 39884 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 39028 KB Output is correct
2 Correct 361 ms 40640 KB Output is correct
3 Correct 51 ms 15604 KB Output is correct
4 Correct 363 ms 38768 KB Output is correct
5 Correct 345 ms 39800 KB Output is correct
6 Correct 365 ms 38884 KB Output is correct
7 Correct 369 ms 39912 KB Output is correct
8 Correct 379 ms 38664 KB Output is correct
9 Correct 367 ms 38592 KB Output is correct
10 Correct 364 ms 41160 KB Output is correct
11 Correct 386 ms 39484 KB Output is correct
12 Correct 377 ms 40332 KB Output is correct
13 Correct 364 ms 38592 KB Output is correct
14 Correct 359 ms 40640 KB Output is correct
15 Correct 358 ms 40384 KB Output is correct
16 Correct 357 ms 38684 KB Output is correct
17 Correct 362 ms 39884 KB Output is correct
18 Correct 486 ms 39008 KB Output is correct
19 Correct 485 ms 40636 KB Output is correct
20 Correct 51 ms 15728 KB Output is correct
21 Correct 402 ms 38848 KB Output is correct
22 Correct 471 ms 39104 KB Output is correct
23 Correct 380 ms 38968 KB Output is correct
24 Correct 497 ms 39616 KB Output is correct
25 Correct 352 ms 38808 KB Output is correct
26 Correct 437 ms 38592 KB Output is correct
27 Correct 555 ms 41228 KB Output is correct
28 Correct 468 ms 39060 KB Output is correct
29 Correct 476 ms 40648 KB Output is correct
30 Correct 396 ms 38592 KB Output is correct
31 Correct 422 ms 40548 KB Output is correct
32 Correct 361 ms 40384 KB Output is correct
33 Correct 515 ms 38652 KB Output is correct
34 Correct 413 ms 39872 KB Output is correct