Submission #1154398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154398		Pichon5	Meteors (POI11_met)	C++20	74 / 100	1051 ms	86292 KiB

met

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N=3e5+5;
 
int n, m, q;
int a[N], reqd[N];
int ql[N], qr[N], qa[N];
int lo[N], mid[N], hi[N];
vector<int> vec[N], owns[N];
int bit[N];
 
void update(int idx, int val)
{
	while(idx<=m)
	{
		bit[idx]+=val;
		idx+=idx&-idx;
	}
}
 
int pref(int idx)
{
	int ans=0;
	while(idx>0)
	{
		ans+=bit[idx];
		idx-=idx&-idx;
	}
	return ans;
}
 
void clear()
{
	memset(bit, 0, sizeof(bit));	
}
 
void apply(int idx)
{
	if(ql[idx] <= qr[idx])
		update(ql[idx], qa[idx]), update(qr[idx]+1, -qa[idx]);
	else
	{
		update(1, qa[idx]);
		update(qr[idx]+1, -qa[idx]);
		update(ql[idx], qa[idx]);
	}
}
 
bool check(int idx)
{
	int req=reqd[idx];
	for(auto &it:owns[idx])
	{
		req-=pref(it);
		if(req<0)
			break;
	}
	if(req<=0)
		return 1;
	return 0;
}	
 
void work()
{	
	for(int i=1;i<=q;i++)
		vec[i].clear();
	for(int i=1;i<=n;i++)
		if(mid[i]>0)
			vec[mid[i]].push_back(i);
	clear();
	for(int i=1;i<=q;i++)
	{
		apply(i);
		for(auto &it:vec[i])
		{
			if(check(it))
				hi[it]=i;
			else
				lo[it]=i+1;
		}
	}
}
 
void parallel_binary()
{
	for(int i=1;i<=n;i++)
		lo[i]=1, hi[i]=q+1;
	bool changed = 1;
	while(changed)
	{
		changed=0;
		for(int i=1;i<=n;i++)
		{
			if(lo[i]<hi[i])
			{
				changed=1;
				mid[i]=(lo[i] + hi[i])/2;
			}	
			else
				mid[i]=-1;
		}
		work();
	}
}	
 
int32_t main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
		owns[a[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)
		cin>>reqd[i];
	cin>>q;
	for(int i=1;i<=q;i++)
		cin>>ql[i]>>qr[i]>>qa[i];
	parallel_binary();
	for(int i=1;i<=n;i++)
	{
		if(lo[i]<=q)
			cout<<lo[i]<<endl;
		else
			cout<<"NIE"<<endl;
	}
	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: 0 / 13
• Subtask 8: 0 / 13