Submission #750352

#	Time	Username	Problem	Language	Result	Execution time	Memory
750352		emptypringlescan	Meteors (POI11_met)	C++17	100 / 100	1906 ms	35108 KiB

met

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll fenw[300005];
void update(int x, ll v){
	for(;x<300005;x+=x&-x) fenw[x]+=v;
}
ll query(int x){
	ll ret=0;
	for(;x;x-=x&-x) ret+=fenw[x];
	return ret;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	vector<int> arr[n+1];
	for(int i=1; i<=m; i++){
		int x;
		cin >> x;
		arr[x].push_back(i);
	}
	ll need[n+1];
	for(int i=1; i<=n; i++) cin >> need[i];
	int q;
	cin >> q;
	pair<pair<int,int>,ll> qu[q+1];
	for(int i=1; i<=q; i++){
		int a,b;
		ll c;
		cin >> a >> b >> c;
		qu[i]={{a,b},c};
	}
	int lo[n+1],hi[n+1];
	for(int i=1; i<=n; i++) lo[i]=1,hi[i]=q+1;
	for(int k=0; k<20; k++){
		pair<int,int> whr[n+1];
		for(int i=1; i<=n; i++){
			whr[i]={(lo[i]+hi[i])/2,i};
		}
		sort(whr+1,whr+n+1);
		int c=1;
		for(int i=0; i<300005; i++) fenw[i]=0;
		for(int i=1; i<=n; i++){
			if(lo[whr[i].second]==hi[whr[i].second]) continue;
			while(c<=min(q,whr[i].first)){
				if(qu[c].first.first<=qu[c].first.second){
					update(qu[c].first.first,qu[c].second);
					update(qu[c].first.second+1,-qu[c].second);
				}
				else{
					update(1,qu[c].second);
					update(qu[c].first.second+1,-qu[c].second);
					update(qu[c].first.first,qu[c].second);
					update(m+1,-qu[c].second);
				}
				c++;
			}
			ll heh=0;
			for(int j:arr[whr[i].second]) heh+=query(j);
			if(heh>=need[whr[i].second]) hi[whr[i].second]=whr[i].first;
			else lo[whr[i].second]=whr[i].first+1;
		}
	}
	for(int i=1; i<=n; i++){
		if(lo[i]==q+1) cout << "NIE\n";
		else cout << lo[i] << '\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