oj.uz

Submission #1001481

# Submission time Handle Problem Language Result Execution time Memory
1001481 2024-06-19T04:04:57 Z wangziyanmo Meteors (POI11_met) C++14
100 / 100
 1232 ms 51392 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();
		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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19292 KB Output is correct
2 Correct 4 ms 19292 KB Output is correct
3 Correct 4 ms 19396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19288 KB Output is correct
2 Correct 3 ms 19292 KB Output is correct
3 Correct 4 ms 19292 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 20060 KB Output is correct
2 Correct 139 ms 24300 KB Output is correct
3 Correct 92 ms 22240 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 20620 KB Output is correct
2 Correct 119 ms 21768 KB Output is correct
3 Correct 146 ms 24528 KB Output is correct
4 Correct 21 ms 21188 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 20304 KB Output is correct
2 Correct 168 ms 24720 KB Output is correct
3 Correct 50 ms 19800 KB Output is correct
4 Correct 105 ms 22448 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 19908 KB Output is correct
2 Correct 142 ms 21964 KB Output is correct
3 Correct 85 ms 21084 KB Output is correct
4 Correct 136 ms 25192 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 30984 KB Output is correct
2 Correct 127 ms 29508 KB Output is correct
3 Correct 333 ms 21596 KB Output is correct
4 Correct 1107 ms 48644 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 29892 KB Output is correct
2 Correct 581 ms 27984 KB Output is correct
3 Correct 62 ms 22620 KB Output is correct
4 Correct 1232 ms 51392 KB Output is correct