Submission #1140905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140905		dragdam	Meteors (POI11_met)	C++17	100 / 100	623 ms	46232 KiB

met

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3e5+5;


int n, m, k;
int a[MAXN], p[MAXN];
array<int,3> q[MAXN];
vector<int> g[MAXN];
int ans[MAXN];

int f[MAXN];
void add(int x, int y){
	for(int i = x; i < MAXN; i |= i+1) f[i] += y;
}
void add(int l, int r, int x){
	if(r < l){
		add(1, r, x);
		add(l, m+1, x);
	}
	else{
		add(l,x);
		add(r+1,-x);
	}
}
int sum(int x){
	int r = 0;
	for(int i = x; i >= 0; i = (i&i+1)-1) r += f[i];
	return r;
}

void bs(int l, int r, vector<int> c){
	if(l > r) return;
	int mid = (l+r)/2;
	for(int i = l; i <= mid; ++i){
		add(q[i][0], q[i][1], q[i][2]);
	}
	vector<int> v[2];
	for(int x : c){
		int t = 0;
		for(int k : g[x]){
			if(t >= p[x]) break;
			t += sum(k);
		}
		if(t >= p[x]){
			ans[x] = mid;
			v[0].push_back(x);
		}
		else{
			p[x] -= t;
			v[1].push_back(x);
		}
	}
	for(int i = l; i <= mid; ++i){
		add(q[i][0], q[i][1], -q[i][2]);
	}
	bs(mid+1,r,v[1]);
	bs(l,mid-1,v[0]);
}

void solve(){
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		cin >> a[i];
		g[a[i]].push_back(i);
	}
	vector<int> v(n);
	for(int i = 1; i <= n; ++i){
		cin >> p[i];
		v[i-1] = i;
	}
	cin >> k;
	for(int i = 1; i <= k; ++i){
		cin >> q[i][0] >> q[i][1] >> q[i][2];
	}
	bs(1,k,v);
	for(int i = 1; i <= n; ++i){
		if(ans[i]) cout << ans[i] << '\n';
		else cout << "NIE\n";
	}
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int32_t qqq=1;
    //cin >> qqq;
    while(qqq--)solve();
    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: 13 / 13
• Subtask 8: 13 / 13