oj.uz

Submission #1089434

# Submission time Handle Problem Language Result Execution time Memory
1089434 2024-09-16T13:39:49 Z Mike_Vu Meteors (POI11_met) C++14
74 / 100
 963 ms 31464 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;
    }
} 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;
int 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;
    }
    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 = BIT(m);
        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]) {
                    sum += bit.query(station);
                }
//                cout << sum << "\n";
                if (sum >= goal[id]) {
                    if (ans[id] == -1 || mid[id] < ans[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 6 ms 8540 KB Output is correct
3 Correct 6 ms 8540 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 11332 KB Output is correct
2 Correct 105 ms 12648 KB Output is correct
3 Correct 77 ms 11992 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 11852 KB Output is correct
2 Correct 81 ms 11868 KB Output is correct
3 Correct 107 ms 12612 KB Output is correct
4 Correct 27 ms 10844 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 11328 KB Output is correct
2 Correct 83 ms 12644 KB Output is correct
3 Correct 35 ms 9940 KB Output is correct
4 Correct 80 ms 12256 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 11384 KB Output is correct
2 Correct 91 ms 11956 KB Output is correct
3 Correct 50 ms 11724 KB Output is correct
4 Correct 103 ms 12732 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 959 ms 31464 KB Output is correct
2 Incorrect 610 ms 25852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 30804 KB Output is correct
2 Incorrect 643 ms 24388 KB Output isn't correct
3 Halted 0 ms 0 KB -