oj.uz

답안 #773938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
773938 2023-07-05T09:46:10 Z loctildore 휴가 (IOI14_holiday) C++14
100 / 100
 1798 ms 12604 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
// trans rights
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)

struct node{
    int l, r;
    ll val;
    int cnt;
    node *lft, *rht;
    node (int tl, int tr): l(tl), r(tr), val(0), cnt(0) {
        if (l + 1 == r) {
            lft = rht = NULL;
            return;
        }
        lft = new node(l, (l + r) / 2);
        rht = new node((l + r) / 2, r);
    }

    void upd(int p, int x) {
        if (p < l || p >= r) return;
        if (l + 1 == r) {
            val += x;
            cnt = (bool) val;
            return;
        }
        lft->upd(p, x);
        rht->upd(p, x);
        val = lft->val + rht->val;
        cnt = lft->cnt + rht->cnt;
    }

    ll qry(int& x) {
        if (x <= 0) return 0;
        if (x >= cnt) {
            x -= cnt;
            return val;
        }
        ll tmp = rht->qry(x);
        return tmp + lft->qry(x);
    }
}* root;

int strt, d;
int pos[100069], val[100069];

int cl = 0, cr = 0;

bool flpd[100069];
void flp(int x) {
    if (flpd[x]) root->upd(pos[x], -val[x]);
    else root->upd(pos[x], val[x]);
    flpd[x] ^= 1;
}

void st(int tl, int tr) {
    if (tl > tr) swap(tl, tr);
    while (cl > tl) flp(--cl);
    while (cl < tl) flp(cl++);
    while (cr > tr) flp(cr--);
    while (cr < tr) flp(++cr);
}

ll fnd(int l, int r, int sl, int sr) {
    if (r < l) return 0;
    int m = (l + r) / 2;
    pair<ll, int> maxi = {INT_MIN, -1};
    for (int i = sl; i <= sr; i++) {
        st(m, i);
        int tmp = d - abs(strt - m) - abs(m - i);
        ll vl = tmp;
        if (tmp > 0) vl = root->qry(tmp); //let's hope this works
        //cout<<m<<':'<<i<<'!'<<vl<<'?'<<root->val<<endl;
        maxi = max(maxi, {vl, i});
    }
    return max(maxi.f, max(fnd(l, m - 1, sl, maxi.s), fnd(m + 1, r, maxi.s, sr)));
}

long long int findMaxAttraction(int n, int start, int D, int attraction[]) {
    strt = start; d = D;
    vector<pair<int, int>> srt;
    for (int i = 0; i < n; i++) {
        val[i] = attraction[i];
        srt.push_back({val[i], i});
    }
    sort(all(srt));
    for (int i = 0; i < n; i++) {
        pos[srt[i].s] = i;
    }

    root = new node(0, n);
    flp(0);

    return max(fnd(0, strt, 0, n - 1), fnd(strt, n - 1, 0, n - 1));
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 460 ms 11848 KB Output is correct
2 Correct 473 ms 11892 KB Output is correct
3 Correct 480 ms 11932 KB Output is correct
4 Correct 467 ms 11848 KB Output is correct
5 Correct 715 ms 11052 KB Output is correct
6 Correct 163 ms 3848 KB Output is correct
7 Correct 358 ms 6476 KB Output is correct
8 Correct 442 ms 7620 KB Output is correct
9 Correct 112 ms 2896 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 980 KB Output is correct
2 Correct 9 ms 980 KB Output is correct
3 Correct 11 ms 992 KB Output is correct
4 Correct 16 ms 964 KB Output is correct
5 Correct 15 ms 968 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 5 ms 696 KB Output is correct
8 Correct 5 ms 696 KB Output is correct
9 Correct 5 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 494 ms 12568 KB Output is correct
2 Correct 458 ms 12604 KB Output is correct
3 Correct 510 ms 5964 KB Output is correct
4 Correct 16 ms 1032 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 5 ms 696 KB Output is correct
8 Correct 1777 ms 12556 KB Output is correct
9 Correct 1798 ms 12504 KB Output is correct