oj.uz

답안 #1043947

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1043947 2024-08-05T05:06:11 Z 정민찬(#11007) Measures (CEOI22_measures) C++17
100 / 100
 353 ms 27080 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

const ll inf = 2e18;

struct LazySegmentTree{
    vector<ll> tree;
    vector<ll> lazy;
    void init(ll n) {
        ll sz = 1 << __lg(n-1) + 2;
        tree.assign(sz, -inf);
        lazy.assign(sz, 0);
    }
    void propagate(ll node, ll s, ll e) {
        tree[node] += lazy[node];
        if (s != e) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    void update(ll node, ll s, ll e, ll l, ll r, ll v) {
        propagate(node, s, e);
        if (l > e || s > r) return;
        if (l <= s && e <= r) {
            lazy[node] = v;
            propagate(node, s, e);
            return;
        }
        ll mid = s + e >> 1;
        update(node*2, s, mid, l, r, v);
        update(node*2+1, mid+1, e, l, r, v);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
    void modify(ll node, ll s, ll e, ll tar, ll val) {
        propagate(node, s, e);
        if (s > tar || tar > e) return;
        if (s == e) {
            tree[node] = val;
            return;
        }
        ll mid = s + e >> 1;
        modify(node*2, s, mid, tar, val);
        modify(node*2+1, mid+1, e, tar, val);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
    ll query(ll node, ll s, ll e, ll l, ll r) {
        propagate(node, s, e);
        if (l > e || s > r) return -inf;
        if (l <= s && e <= r) return tree[node];
        ll mid = s + e >> 1;
        return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
    }
};

struct Fenwick{
    vector<ll> tree;
    void init(ll n) {
        tree.assign(n+1, 0);
    }
    void upd(ll i, ll v, ll n) {
        while (i <= n) {
            tree[i] += v;
            i += i & -i;
        }
    }
    ll qry(ll i) {
        ll ret = 0;
        while (i) {
            ret += tree[i];
            i -= i & -i;
        }
        return ret;
    }
};

LazySegmentTree seg1, seg2;
Fenwick fwt;

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    ll N, M, D;
    cin >> N >> M >> D;
    vector<pll> t;
    vector<ll> a(N);
    for (ll i=0; i<N; i++) {
        cin >> a[i];
    }
    vector<ll> b(M);
    for (ll i=0; i<M; i++) {
        cin >> b[i];
        t.push_back({b[i], N+i});
    }
    sort(a.begin(), a.end());
    for (ll i=0; i<N; i++) {
        t.push_back({a[i], i});
    }
    sort(t.begin(), t.end());
    seg1.init(N+M); seg2.init(N+M);
    fwt.init(N+M);
    ll ans = 0;
    for (ll i=0; i<N; i++) {
        ll idx = lower_bound(t.begin(), t.end(), pll{a[i], i}) - t.begin() + 1;
        seg1.modify(1, 1, N+M, idx, i*D - a[i]);
        seg2.modify(1, 1, N+M, idx, -i*D + a[i]);
        fwt.upd(idx, 1, N+M);
        ans = max(ans, seg2.tree[1] + D*i - a[i]);
    }
    for (ll i=0; i<M; i++) {
        ll idx = lower_bound(t.begin(), t.end(), pll{b[i], N+i}) - t.begin() + 1;
        ll ord = fwt.qry(idx);
        seg1.update(1, 1, N+M, idx+1, N+M, D);
        seg2.update(1, 1, N+M, idx+1, N+M, -D);
        seg1.modify(1, 1, N+M, idx, ord*D - b[i]);
        seg2.modify(1, 1, N+M, idx, -ord*D + b[i]);
        fwt.upd(idx, 1, N+M);
        ans = max(ans, seg1.query(1, 1, N+M, idx, N+M) + seg2.query(1, 1, N+M, 1, idx));
        if (ans % 2 == 0) cout << ans / 2 << ' ';
        else cout << ans / 2 << ".5 ";
    }


    return 0;
}

Compilation message

Main.cpp: In member function 'void LazySegmentTree::init(ll)':
Main.cpp:14:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   14 |         ll sz = 1 << __lg(n-1) + 2;
      |                      ~~~~~~~~~~^~~
Main.cpp: In member function 'void LazySegmentTree::update(ll, ll, ll, ll, ll, ll)':
Main.cpp:34:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         ll mid = s + e >> 1;
      |                  ~~^~~
Main.cpp: In member function 'void LazySegmentTree::modify(ll, ll, ll, ll, ll)':
Main.cpp:46:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         ll mid = s + e >> 1;
      |                  ~~^~~
Main.cpp: In member function 'll LazySegmentTree::query(ll, ll, ll, ll, ll)':
Main.cpp:55:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         ll mid = s + e >> 1;
      |                  ~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 660 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 660 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 98 ms 22984 KB Output is correct
10 Correct 85 ms 23748 KB Output is correct
11 Correct 96 ms 23240 KB Output is correct
12 Correct 91 ms 23492 KB Output is correct
13 Correct 87 ms 22988 KB Output is correct
14 Correct 94 ms 23388 KB Output is correct
15 Correct 116 ms 22980 KB Output is correct
16 Correct 96 ms 23564 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 24000 KB Output is correct
2 Correct 212 ms 26660 KB Output is correct
3 Correct 206 ms 26560 KB Output is correct
4 Correct 206 ms 24260 KB Output is correct
5 Correct 238 ms 26060 KB Output is correct
6 Correct 233 ms 24260 KB Output is correct
7 Correct 217 ms 25540 KB Output is correct
8 Correct 216 ms 23780 KB Output is correct
9 Correct 201 ms 23744 KB Output is correct
10 Correct 229 ms 26948 KB Output is correct
11 Correct 221 ms 24516 KB Output is correct
12 Correct 208 ms 25532 KB Output is correct
13 Correct 208 ms 23748 KB Output is correct
14 Correct 196 ms 26040 KB Output is correct
15 Correct 204 ms 25780 KB Output is correct
16 Correct 201 ms 23748 KB Output is correct
17 Correct 212 ms 25820 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 24000 KB Output is correct
2 Correct 212 ms 26660 KB Output is correct
3 Correct 206 ms 26560 KB Output is correct
4 Correct 206 ms 24260 KB Output is correct
5 Correct 238 ms 26060 KB Output is correct
6 Correct 233 ms 24260 KB Output is correct
7 Correct 217 ms 25540 KB Output is correct
8 Correct 216 ms 23780 KB Output is correct
9 Correct 201 ms 23744 KB Output is correct
10 Correct 229 ms 26948 KB Output is correct
11 Correct 221 ms 24516 KB Output is correct
12 Correct 208 ms 25532 KB Output is correct
13 Correct 208 ms 23748 KB Output is correct
14 Correct 196 ms 26040 KB Output is correct
15 Correct 204 ms 25780 KB Output is correct
16 Correct 201 ms 23748 KB Output is correct
17 Correct 212 ms 25820 KB Output is correct
18 Correct 349 ms 24252 KB Output is correct
19 Correct 353 ms 25828 KB Output is correct
20 Correct 220 ms 26052 KB Output is correct
21 Correct 236 ms 24000 KB Output is correct
22 Correct 261 ms 24244 KB Output is correct
23 Correct 208 ms 24040 KB Output is correct
24 Correct 305 ms 24768 KB Output is correct
25 Correct 188 ms 24000 KB Output is correct
26 Correct 301 ms 23872 KB Output is correct
27 Correct 324 ms 27080 KB Output is correct
28 Correct 240 ms 24780 KB Output is correct
29 Correct 269 ms 25532 KB Output is correct
30 Correct 250 ms 24608 KB Output is correct
31 Correct 254 ms 26488 KB Output is correct
32 Correct 221 ms 26568 KB Output is correct
33 Correct 288 ms 23748 KB Output is correct
34 Correct 231 ms 25384 KB Output is correct