제출 #1128536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128536		rasbery303	새로운 문제 (POI11_met)	C++20	100 / 100	1310 ms	59132 KiB

met

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

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

void update(int x, long long val){
	while(x<=m){
		tree[x]+=val;
		x+=(x&-x);
 
	}
}
long long read(int x){
	long long s=0;
	while(x>0){
		s+=tree[x];
		x-=(x&-x);
	}
	return s;
}
 
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(qr[x]+1,-qval[x]);
		update(ql[x],qval[x]);
	}
}

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

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

    for (int i = 1; i <= n; ++i){
        l[i] = 1;
        r[i] = k+1;
    }   
    
    bool ok = true;
    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){
        assert(l[i]==r[i]);
        if (l[i] <= k){
            cout << l[i] << '\n';
        } else {
            cout << "NIE\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: 13 / 13
• Subtask 8: 13 / 13