oj.uz

Submission #706148

# Submission time Handle Problem Language Result Execution time Memory
706148 2023-03-06T01:48:11 Z Pring Snowball (JOI21_ho_t2) C++14
0 / 100
 2500 ms 347100 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> pii;

struct SMG {
    int val, tag;
    SMG() {
        val = 0;
        tag = 0;
    }
};

const int MXN = 2005, MXQ = 2005;
int n, q, a[MXN], cl, cr, w[MXN], wei[MXN], d[MXN * MXQ], dil;
pii pos[MXN * MXQ];
SMG smg[MXN * MXQ * 4];
bitset<MXN * MXQ * 4> taga;

void add_tag(int id, int l, int r, int _tag) {
    smg[id].val = (d[r] - d[l]) * _tag;
    smg[id].tag = _tag;
    taga[id] = true;
}

void push(int id, int l, int r) {
    if (!taga[id]) return;
    int mid = (l + r) >> 1;
    add_tag(id * 2 + 1, l, mid, smg[id].tag);
    add_tag(id * 2 + 2, mid, r, smg[id].tag);
    taga[id] = false;
}

void pull(int id, int l, int r) {
    smg[id].val = smg[id * 2 + 1].val + smg[id * 2 + 2].val;
}

void modify(int id, int l, int r, int _l, int _r, int _val) {
    if (_r <= l || r <= _l) return;
    if (_l <= l && r <= _r) {
        add_tag(id, l, r, _val);
        return;
    }
    int mid = (l + r) >> 1;
    push(id, l, r);
    modify(id * 2 + 1, l, mid, _l, _r, _val);
    modify(id * 2 + 2, mid, r, _l, _r, _val);
    pull(id, l, r);
};

int query(int id, int l, int r, int _l, int _r) {
    if (_r <= l || r <= _l) return 0;
    if (_l <= l && r <= _r) return smg[id].val;
    int mid = (l + r) >> 1;
    push(id, l, r);
    return query(id * 2 + 1, l, mid, _l, _r) + query(id * 2 + 2, mid, r, _l, _r);
}

int getAllCoors() {
    int now = 0, C = 1;
    for (int i = 0; i < n; i++) pos[i].first = a[i];
    for (int i = 0; i < q; i++) {
        bool flag = false;
        now += w[i];
        if (now > cr) {
            cr = now;
            flag = true;
        } else if (now < cl) {
            cl = now;
            flag = true;
        }
        if (flag) {
            for (int j = 0; j < n; j++) pos[C * n + j].first = a[j] + now;
            C++;
        }
    }
    cl = 0;
    cr = 0;
    return C * n;
}

void dist() {
    for (int i = 0; i < dil; i++) {
        pos[i].second = i;
    }
    sort(pos, pos + dil);
    // auto it = unique(pos, pos + dil, [](pii a, pii b) {
    //     return a.first == b.first;
    // });
    // dil = it - pos;
    for (int i = 0; i < dil; i++) {
        d[i] = pos[i].first;
        pos[i].first = i;
    }
    sort(pos, pos + dil, [](pii a, pii b) {
        return a.second < b.second;
    });
}

void buildSMG() {
    // build(0, 0, dil - 1);
    add_tag(0, 0, dil - 1, 1);
}

void solve() {
    int now = 0, C = 1;
    for (int i = 0; i < q; i++) {
        bool flag = false;
        now += w[i];
        if (now > cr) {
            cr = now;
            flag = true;
        } else if (now < cl) {
            cl = now;
            flag = true;
        }
        if (flag) {
            int wind = w[i];
            if (wind > 0) {
                for (int j = 0; j < n; j++) {
                    // cout << "DO: " << d[pos[j].first] << ' ' << d[pos[n * C + j].first] << endl;
                    wei[j] += query(0, 0, dil - 1, pos[j].first, pos[n * C + j].first);
                    modify(0, 0, dil - 1, pos[j].first, pos[n * C + j].first, 0);
                }
            } else {
                for (int j = 0; j < n; j++) {
                    // cout << "DO: " << d[pos[j].first] << ' ' << d[pos[n * C + j].first] << endl;
                    wei[j] += query(0, 0, dil - 1, pos[n * C + j].first, pos[j].first);
                    modify(0, 0, dil - 1, pos[n * C + j].first, pos[j].first, 0);
                }
            }
            C++;
        }
        // for (int j = 0; j < n; j++) cout << wei[j] << ' ';
        // cout << endl;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> w[i];
    dil = getAllCoors();
    // cout << dil << endl;
    dist();
    // cout << dil << endl;
    // for (int i = 0; i < dil; i++) cout << d[i] << ' ';
    // cout << endl;
    buildSMG();
    solve();
    for (int i = 0; i < n; i++) cout << wei[i] << '\n';
    return 0;
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 252236 KB Output is correct
2 Correct 133 ms 253036 KB Output is correct
3 Correct 495 ms 261584 KB Output is correct
4 Execution timed out 2597 ms 347100 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 252236 KB Output is correct
2 Correct 133 ms 253036 KB Output is correct
3 Correct 495 ms 261584 KB Output is correct
4 Execution timed out 2597 ms 347100 KB Time limit exceeded
5 Halted 0 ms 0 KB -