Submission #976063

#	Time	Username	Problem	Language	Result	Execution time	Memory
976063		UmairAhmadMirza	Meteors (POI11_met)	C++17	24 / 100	5476 ms	60164 KiB

met

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=3e5+5;
int const mod=1e9+7;

int low[N],high[N];
int target[N];
int owner[N];
vector<int> property[N];
int n,m;
int shower[N][3];
vector<int> query_on_mid[N];

ll seg[4*N];
ll lazy[4*N];

void push(int v,int s,int e)
{
	int lc=v*2,rc=lc+1,mid=(s+e)/2;
	seg[lc]+=lazy[v]*(mid-s),seg[rc]+=lazy[v]*(e-mid);
	lazy[lc]+=lazy[v],lazy[rc]+=lazy[v];
	lazy[v]=0;
}

void update(int node,int l,int r,int val,int s=0,int e=m){
	if(e<=l || r<=s)
		return;
	if(l<=s && e<=r){
		lazy[node]+=val;
		seg[node]+=val*(e-s);
		return;
	}
	int mid=(s+e)/2;
	push(node,s,e);
	update(node*2,l,r,val,s,mid);
	update(node*2+1,l,r,val,mid,e);
	seg[node]=seg[node*2]+seg[node*2+1];
}
ll query(int node,int l,int r,int s=0,int e=m){
	if(e<=l || r<=s)
		return 0;
	if(l<=s && e<=r)
		return seg[node];
	int mid=(s+e)/2;
	push(node,s,e);
	return query(node*2,l,r,s,mid)+query(node*2+1,l,r,mid,e);
}

int main(){
	cin>>n>>m;
	
	for (int i = 0; i < m; ++i){
		cin>>owner[i];
		owner[i]--;
		property[owner[i]].push_back(i);
	}
	
	for(int i=0;i<n;i++)
		cin>>target[i];
	
	int q;
	cin>>q;
	for (int i = 0; i < q; ++i){
		cin>>shower[i][0]>>shower[i][1]>>shower[i][2];
		shower[i][0]--;
	}
	
	for(int i=0;i<n;i++){
		high[i]=q;
		low[i]=-1;
	}

	for(int lg=0;lg<20;lg++){
		for(int i=0;i<q;i++)
			query_on_mid[i].clear();

		for(int i=0;i<n;i++){
			int mid=(high[i]+low[i])/2;
			query_on_mid[mid].push_back(i);
		}

		for(int i=0;i<4*m;i++)//segment tree reset
			seg[i]=lazy[i]=0;

		for(int i=0;i<q;i++){
			if(shower[i][0]>shower[i][1]){
				update(1,shower[i][0],m,shower[i][2]);
				update(1,0,shower[i][1],shower[i][2]);
			}
			else
				update(1,shower[i][0],shower[i][1],shower[i][2]);
			for(auto st:query_on_mid[i]){
				ll sm=0;
				for(auto p:property[st])
					sm+=query(1,p,p+1);
				if(sm>=target[st])
					high[st]=i;
				else
					low[st]=i;
			}
		}
	}

	for(int i=0;i<n;i++){
		if(high[i]==q)
			cout<<"NIE"<<endl;
		else
			cout<<high[i]+1<<endl;
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 12 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13