oj.uz

Submission #1089712

# Submission time Handle Problem Language Result Execution time Memory
1089712 2024-09-17T00:58:38 Z Mike_Vu Meteors (POI11_met) C++14
100 / 100
 1477 ms 37748 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define BITj(x, j) (((x)>>(j))&1)
#define MASK(x) (1LL<<(x))

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct BIT{
    int n;
    vector<ll> bit;
    BIT(int _n = 0) {
        n = _n;
        bit.assign(n+1, 0);
    }
    void upd(int k, int val) {
        while (k <= n) {
            bit[k] += val;
            k += k & (-k);
        }
    }
    void update(int l, int r, int val) {
        if (l <= r){
            upd(l, val);
            upd(r+1, -val);
        }
        else {
            upd(1, val);
            upd(r+1, -val);
            upd(l, val);
        }
    }
    ll query(int k) {
        ll ans = 0;
        while (k > 0) {
            ans += bit[k];
            k -= k & (-k);
        }
        return ans;
    }

    void reset(){
        fill(bit.begin(), bit.end(), 0);
    }
} bit;

struct prediction{
    int l, r, val;
    prediction(int _l, int _r, int _val){
        l = _l;
        r = _r;
        val = _val;
    }
};

const int maxn = 3e5+5;
int n, m, k;
vector<int> states[maxn];
vector<prediction> pred;
ll goal[maxn];

int l[maxn], r[maxn], mid[maxn], ans[maxn];
vector<int> still;

bool cmp(int a, int b) {
    return mid[a] < mid[b];
}

void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        states[x].pb(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> goal[i];
    }
    cin >> k;
    for (int i = 1; i <= k; i++) {
        int l, r, val;
        cin >> l >> r >> val;
        pred.push_back(prediction(l, r, val));
    }
}

void parallel_binsearch() {
    //init
    for (int i = 1; i <= n; i++) {
        l[i] = 1;
        r[i] = k;
    }

    bit = BIT(m);
    while (true) {
        int coustill = 0;
        still.clear();
        for (int i = 1; i <= n; i++) {
            if (l[i] <= r[i]) {
                mid[i] = (l[i]+r[i])>>1;
                ++coustill;
                still.push_back(i);
            }
        }
        if (coustill == 0) break;
        bit.reset();
        sort(still.begin(), still.end(), cmp);
        int j = 0;
        for (int i = 0; i < k; i++) {
            bit.update(pred[i].l, pred[i].r, pred[i].val);
//            cout << pred[i].l<< ' ' << pred[i].r<< ' ' <<  pred[i].val << "\n";
            while (j < (int)still.size() && mid[still[j]] <= i+1) {
                int id = still[j++];
//                cout << id << ' ' << l[id] << ' ' << r[id] << ' ' << mid[id] << ' ';
                ll sum = 0;
                for (int station : states[id]) {
                    if (sum >= goal[id]) break;
                    sum += bit.query(station);
                }
//                cout << sum << "\n";
                if (sum >= goal[id]) {
                    ans[id] = mid[id];
                    r[id] = mid[id]-1;
                }
                else l[id] = mid[id]+1;
//                cout << l[id] << ' ' << r[id] << "\n";
            }
//            if (j == (int)still.size()) break;
        }
//        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    input();
    memset(ans, -1, sizeof(ans));
    parallel_binsearch();
    //cout
    for (int i = 1; i <= n; i++) {
        if (ans[i] == -1) cout << "NIE";
        else cout << ans[i];
        cout << "\n";
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 4 ms 8584 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8596 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 5 ms 8548 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 10964 KB Output is correct
2 Correct 103 ms 12304 KB Output is correct
3 Correct 75 ms 11480 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 11516 KB Output is correct
2 Correct 77 ms 11476 KB Output is correct
3 Correct 100 ms 12288 KB Output is correct
4 Correct 31 ms 10584 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 10960 KB Output is correct
2 Correct 80 ms 12376 KB Output is correct
3 Correct 34 ms 10016 KB Output is correct
4 Correct 82 ms 11976 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 11012 KB Output is correct
2 Correct 93 ms 11732 KB Output is correct
3 Correct 51 ms 10964 KB Output is correct
4 Correct 99 ms 12488 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 924 ms 29620 KB Output is correct
2 Correct 564 ms 23504 KB Output is correct
3 Correct 158 ms 14012 KB Output is correct
4 Correct 1267 ms 35828 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 28848 KB Output is correct
2 Correct 574 ms 22060 KB Output is correct
3 Correct 133 ms 14540 KB Output is correct
4 Correct 1477 ms 37748 KB Output is correct