oj.uz

Submission #1001474

# Submission time Handle Problem Language Result Execution time Memory
1001474 2024-06-19T04:01:03 Z wangziyanmo Meteors (POI11_met) C++14
0 / 100
 715 ms 37692 KB 
#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();
		/*
		cout<<k.l<<' '<<k.r<<"\n";
		for (auto x:k.v){
			cout<<x<<' ';
		}
		cout<<"\n\n";
		*/
		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;
		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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 19292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 19288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 21072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 21476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 21076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 20900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 636 ms 37692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 715 ms 37108 KB Output isn't correct
2 Halted 0 ms 0 KB -