Submission #1217302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217302		reginox	Meteors (POI11_met)	C++20	74 / 100	1748 ms	43016 KiB

met

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
struct Fenwick{
	int n; vector<vector<ll>> t;
	Fenwick(int n){
		this->n = n;
		t.assign(n+1, vector<ll>(2, 0));
	}
    void ass(int n){
        this->n = n;
        t.assign(n+1, vector<ll>(2, 0));
    }
	void upd(int tp, int id, ll x){
		for(int i = id; i <= n; i+=i&(-i)) t[i][tp]+=x;
	}
	void add(int l, int r, ll x){
		upd(0, l, x); upd(0, r+1, -x);
		upd(1, l, x*(l-1)); upd(1, r+1, -x*r);	
	}
	ll sum(int tp, int id){
		ll res = 0;
		for(int i = id; i > 0; i-=i&(-i)) res+=t[i][tp];
		return res;
	}
	ll get(int x){
		return sum(0, x)*(ll)x  - sum(1, x);
	}
	ll query(int a, int b){
		return get(b) - get(a-1);
	}
};

int n, m, q;
vector<pi> e; vi ff;
vector<vi> st;
vi tar;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    tar.resize(n); st.resize(n+1);
    for(int i = 0; i < m; i++){
        int x; cin >> x;
        st[x].push_back(i+1);
    }
    for(auto &x:tar) cin >> x;
    tar.insert(tar.begin(), 0);
    cin >> q;
    ff.resize(q); e.resize(q);
    for(int i = 0; i < q; i++)
        cin >> e[i].first >> e[i].second >> ff[i];
    vi L(n, 0), R(n, q+1);
    vector<vi> c(q+1);
    Fenwick f(m);
    while(true){
        bool has = false;
        for(int i = 0; i < n; i++){
            if(L[i] < R[i]){
                has = true;
                int m = (L[i] + R[i])/2;
                c[m].push_back(i+1);
            }
        }
        if(!has) break;
        for(int i = 0; i <= q; i++){
            if(i > 0){
                int l = e[i-1].first, r = e[i-1].second;
                if(l <= r){
                    f.add(l, r, ff[i-1]);
                }
                else{
                    f.add(l, m, ff[i-1]);
                    f.add(1, r, ff[i-1]);
                }
            }
            // cerr << "dit\n";
            for(auto x:c[i]){
                ll su = 0;
                for(auto y:st[x]){
                    su += f.query(y, y);
                }
                if(su >= tar[x]) R[x-1] = i;
                else L[x-1] = i+1;
            }
            c[i].clear();
        }
        f.ass(m);
    }
    for(int i = 0; i < n; i++){
        if(L[i] > q) cout << "NIE\n";
        else cout << L[i] << "\n"; 
    }
    return 0;
}

• 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