oj.uz

Submission #750352

# Submission time Handle Problem Language Result Execution time Memory
750352 2023-05-29T12:23:22 Z emptypringlescan Meteors (POI11_met) C++17
100 / 100
 1906 ms 35108 KB 
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll fenw[300005];
void update(int x, ll v){
	for(;x<300005;x+=x&-x) fenw[x]+=v;
}
ll query(int x){
	ll ret=0;
	for(;x;x-=x&-x) ret+=fenw[x];
	return ret;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	vector<int> arr[n+1];
	for(int i=1; i<=m; i++){
		int x;
		cin >> x;
		arr[x].push_back(i);
	}
	ll need[n+1];
	for(int i=1; i<=n; i++) cin >> need[i];
	int q;
	cin >> q;
	pair<pair<int,int>,ll> qu[q+1];
	for(int i=1; i<=q; i++){
		int a,b;
		ll c;
		cin >> a >> b >> c;
		qu[i]={{a,b},c};
	}
	int lo[n+1],hi[n+1];
	for(int i=1; i<=n; i++) lo[i]=1,hi[i]=q+1;
	for(int k=0; k<20; k++){
		pair<int,int> whr[n+1];
		for(int i=1; i<=n; i++){
			whr[i]={(lo[i]+hi[i])/2,i};
		}
		sort(whr+1,whr+n+1);
		int c=1;
		for(int i=0; i<300005; i++) fenw[i]=0;
		for(int i=1; i<=n; i++){
			if(lo[whr[i].second]==hi[whr[i].second]) continue;
			while(c<=min(q,whr[i].first)){
				if(qu[c].first.first<=qu[c].first.second){
					update(qu[c].first.first,qu[c].second);
					update(qu[c].first.second+1,-qu[c].second);
				}
				else{
					update(1,qu[c].second);
					update(qu[c].first.second+1,-qu[c].second);
					update(qu[c].first.first,qu[c].second);
					update(m+1,-qu[c].second);
				}
				c++;
			}
			ll heh=0;
			for(int j:arr[whr[i].second]) heh+=query(j);
			if(heh>=need[whr[i].second]) hi[whr[i].second]=whr[i].first;
			else lo[whr[i].second]=whr[i].first+1;
		}
	}
	for(int i=1; i<=n; i++){
		if(lo[i]==q+1) cout << "NIE\n";
		else cout << lo[i] << '\n';
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 4 ms 2660 KB Output is correct
3 Correct 4 ms 2704 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3960 KB Output is correct
2 Correct 154 ms 5312 KB Output is correct
3 Correct 118 ms 4568 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 4280 KB Output is correct
2 Correct 116 ms 4260 KB Output is correct
3 Correct 167 ms 5308 KB Output is correct
4 Correct 45 ms 4044 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 4060 KB Output is correct
2 Correct 166 ms 5384 KB Output is correct
3 Correct 77 ms 3448 KB Output is correct
4 Correct 125 ms 4832 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3796 KB Output is correct
2 Correct 156 ms 4332 KB Output is correct
3 Correct 76 ms 3816 KB Output is correct
4 Correct 173 ms 5552 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 16444 KB Output is correct
2 Correct 224 ms 16480 KB Output is correct
3 Correct 467 ms 8944 KB Output is correct
4 Correct 1843 ms 32280 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 15376 KB Output is correct
2 Correct 477 ms 15016 KB Output is correct
3 Correct 74 ms 9224 KB Output is correct
4 Correct 1906 ms 35108 KB Output is correct