Submission #1089434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089434		Mike_Vu	Meteors (POI11_met)	C++14	74 / 100	963 ms	31464 KiB

met

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13