oj.uz

Submission #976074

# Submission time Handle Problem Language Result Execution time Memory
976074 2024-05-06T07:05:08 Z UmairAhmadMirza Meteors (POI11_met) C++17
24 / 100
 6000 ms 52188 KB 
#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,ll 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"<<'\n';
		else
			cout<<high[i]+1<<'\n';
	}
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20824 KB Output is correct
2 Correct 12 ms 20828 KB Output is correct
3 Correct 12 ms 20828 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20828 KB Output is correct
2 Correct 11 ms 20824 KB Output is correct
3 Incorrect 12 ms 21084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 25936 KB Output is correct
2 Incorrect 691 ms 27716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 27176 KB Output is correct
2 Correct 580 ms 26984 KB Output is correct
3 Correct 613 ms 27864 KB Output is correct
4 Correct 196 ms 26820 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 26444 KB Output is correct
2 Incorrect 557 ms 28324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 25372 KB Output is correct
2 Incorrect 549 ms 26812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5610 ms 52188 KB Output is correct
2 Incorrect 3487 ms 40916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6022 ms 50524 KB Time limit exceeded
2 Halted 0 ms 0 KB -