제출 #1001481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001481		wangziyanmo	Meteors (POI11_met)	C++14	100 / 100	1232 ms	51392 KiB

met

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int mxn=300000;
vector<int> belong[mxn+10];
int tar[mxn+10];
int l[mxn+10],r[mxn+10],x[mxn+10];
int tree[mxn+10];
int ans[mxn+10];

struct node{
	int l,r;
	vector<int> v;
};
 
void add(int x,int num){
	if (x>mxn) return;
	while (x<=mxn){
		tree[x]+=num;
		x+=x&(-x);
	}
}
 
int que(int x){
	int ans=0;
	while (x>0){
		ans+=tree[x];
		x-=x&(-x);
	}
	return ans;
}
 
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	signed n,m;cin>>n>>m;
	for (signed i=1;i<=m;i++){
		signed x;cin>>x;
		belong[x].push_back(i);
	}
	for (signed i=1;i<=n;i++){
		cin>>tar[i];
	}
	signed q;cin>>q;
	for (signed i=1;i<=q;i++){
		cin>>l[i]>>r[i]>>x[i];
	}
	queue<node> evt;
	vector<int> vt;
	for (int i=1;i<=n;i++) vt.push_back(i);
	evt.push({1,q+1,vt});
	int tme=0;
	while (!evt.empty()){
		auto k=evt.front();evt.pop();
		if (k.l==k.r){
			for (auto x:k.v){
				ans[x]=k.l;
			}
			continue;
		}
		int mid=k.l+(k.r-k.l)/2;
		if (tme>mid){
			tme=0;
			memset(tree,0,sizeof(tree));
		}
		while (tme<mid){
			tme++;
			add(l[tme],x[tme]);add(r[tme]+1,-x[tme]);
			if (l[tme]>r[tme]) add(1,x[tme]);
		}
		vector<int> up,down;
		for (auto x:k.v){
			int t=tar[x];
			for (auto a:belong[x]){
				t-=que(a);
				if (t<=0) break;
			}
			if (t<=0) down.push_back(x);
			else up.push_back(x);
		}
		if (!down.empty()) evt.push({k.l,mid,down});
		if (!up.empty()) evt.push({mid+1,k.r,up});
	}
	for (signed i=1;i<=n;i++){
		if (ans[i]==q+1) cout<<"NIE\n";
		else cout<<ans[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