Submission #1304771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304771		Joseph0121	Meteors (POI11_met)	C++20	74 / 100	663 ms	34092 KiB

met

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5+5;
int meteor[maxn]; //m
int want[maxn]; //n
int L[maxn], R[maxn], ans[maxn]; //n
int N,M;
vector<array<int,3>> events;
vector<int> stations[maxn];
bool check(){
	for(int i = 1;i<=N;i++){
		if(L[i] <= R[i]) return false;
	}
	return true;
}
struct BIT{
	vector<int> bit; int n;
	BIT(int n){
		bit.resize(n,0);
	}
	
	void upd(int x, int v){
		if(x > bit.size()) return;
		for(;x<bit.size();x+=(-x&x)) bit[x]+=v;
	}
	int qry(int x){
		int sum = 0;
		for(;x;x-=(-x&x)) sum+=bit[x];
		return sum;
	}
	void upd_range(int l, int r, int v){
		if(l<=r){
			upd(l,v); upd(r+1,-v);
		}
		else{
			upd(l,v); upd(M+1,-v); upd(1,v); upd(r+1,-v);
		}
	}
};
main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cin>>N>>M;
	for(int i = 1;i<=M;i++){
		 cin>>meteor[i];
		 stations[meteor[i]].push_back(i);
	}
	for(int i = 1;i<=N;i++){
		 cin>>want[i];
		 ans[i] = -1;
	}
	
	int Q; cin>>Q;
	for(int i = 1;i<=Q;i++){
		int l, r, v; cin>>l>>r>>v;
		events.push_back({l,r,v});
	}
	for(int i = 1;i<=N;i++){
		L[i] = 1; R[i] = Q;
	}
	while(!check()){
		vector<int> num(N+1,0), mid(N+1,0);
		vector<vector<int>> query(Q+1);
		BIT bit(M+1);
		for(int i = 1;i<=N;i++){
			if(L[i] > R[i]) continue;
			mid[i] = (L[i]+R[i])/2;
			query[mid[i]].push_back(i);
		}
		for(int i = 1;i<=Q;i++){
			int l = events[i-1][0], r = events[i-1][1], v = events[i-1][2];
			// cout<<l<<" "<<r<<" "<<v<<endl;
			bit.upd_range(l,r,v);
			
			for(auto j: query[i]){
				//j is the indexed numbers
				for(auto k: stations[j]){
					 num[j]+=bit.qry(k);
				}
				// cout<<endl;
			}
			// for(int j = 1;j<=M;j++) cout<<bit.qry(j)-bit.qry(j-1)<<" ";
			// cout<<endl;
		}
		// exit(0);
		// for(int i = 1;i<=N;i++) cout<<num[i]<<" "; cout<<endl;
		for(int i = 1;i<=N;i++){
			if(L[i] > R[i]) continue;
			if(num[i] < want[i]){
				L[i] = mid[i]+1;
			}
			else{
				R[i] = mid[i]-1;
				ans[i] = mid[i];
			}
		}
	}
	
	for(int i = 1;i<=N;i++){
		if(ans[i]!=-1) cout<<ans[i]<<"\n";
		else cout<<"NIE"<<"\n";
	}
	
	return 0;
}

Compilation message (stderr)

met.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main() {
      | ^~~~

• 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