Submission #1128527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128527		rasbery303	Meteors (POI11_met)	C++20	0 / 100	6094 ms	28604 KiB

met

#include <iostream>
#include <vector>
using namespace std;
using ll = long long int;

const int maxn = 3e5+1;
int n, m, k;
ll tree[maxn];
vector<ll> a, p, check[maxn], own[maxn];
bool ok = true;
int ql[maxn], qr[maxn], l[maxn], r[maxn];
ll qval[maxn];

void update(int pos, ll val){
    while (pos <= m){
        tree[pos] += val;
        pos += (pos&-pos);
    }
}

void apply(int x){
    if (ql[x] <= qr[x]){
        update(ql[x], qval[x]);
        update(qr[x]+1, -qval[x]);
    } else {
        update(1, qval[x]);
        update(ql[x], qval[x]);
        update(qr[x]+1, -qval[x]);
    }
}

ll read(int x){
    ll sum = 0;
    while(x>0){
        sum += tree[x];
        x -= (x&-x);
    }
    return sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    a.resize(m+1), p.resize(n+1);
    for (int i = 1; i <= m; ++i){
        cin >> a[i];
        own[a[i]].push_back(i);
    }
    
    for (int i = 1; i <= n; ++i)
        cin >> p[i];

    cin >> k;
    for (int i = 1; i <= n; ++i)
        cin >> ql[i] >> qr[i] >> qval[i];

    for (int i = 1; i <= n; ++i){
        l[i] = 1;
        r[i] = k+1;
    }   
    
    while (ok){
        ok = false;

        for (int i = 0; i <= m; ++i)
            tree[i] = 0;
        for (int i = 1; i <= n; ++i){
            if (l[i]!=r[i]){
                int mid = (l[i]+r[i])>>1;
                check[mid].push_back(i);
            }
        }

        for (int q = 1; q <= k; ++q){
            apply(q);

            while(!check[q].empty()){
                ok = true;

                int id = check[q].back();
                check[q].pop_back();
                
                ll sum = 0;
                for (auto sec: own[id]){
                    sum += read(sec);
                    if (sum >= p[id]) break;
                }

                if (sum >= p[id])
                    r[id] = q;
                else
                    l[id] = q+1;
            }
        }
    }
    for (int i = 1; i <= n; ++i){
        if (l[i] <= k){
            cout << l[i] << '\n';
        } else {
            cout << "NIE\n";
        }
    }
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13