Submission #347663

#	Time	Username	Problem	Language	Result	Execution time	Memory
347663		lovro_nidogon1	Meteors (POI11_met)	C++14	0 / 100	53 ms	65540 KiB

met

#include<bits/stdc++.h>
#define breturn return
#define ll unsigned long long
using namespace std;
ll n, m, o[300001], p[300001], a, b, c, q, bn, tour[1048600], laz[1048600], ans[300001]; 
vector<pair<ll, pair<ll, ll> > > midl[3000001], quer;
vector<pair<ll, pair<ll, pair<ll, ll> > > > nx;
vector<ll> v[300001];
bool done; 
void upd(ll ax, ll bx, ll val, ll x = 1, ll l = 0, ll r = bn - 1) {	
//cout << ax << " " << bx << " " << x << " " << l << " " << r << '\n'; 
	if(ax > r or bx < l) breturn;
	if(l >= ax and r <= bx) {
		laz[x] += val;
		breturn;
	} 
	ll mid = (l + r)/2;
	upd(ax, bx, val, x * 2, l, mid);
	upd(ax, bx, val, x * 2 + 1, mid + 1, r);
}
ll query(ll ax, ll bx, ll x = 1, ll l = 0, ll r = bn - 1) {

	if(ax > r or bx < l) breturn 0;;
	if(l >= ax and r <= bx) {
		tour[x] += laz[x];
		laz[x] = 0;
		breturn tour[x];
	} 
	laz[x * 2] += laz[x];
	laz[x * 2 + 1] += laz[x];
	laz[x] = 0;
	ll mid = (l + r)/2;
	breturn query(ax, bx, x * 2, l, mid) + query(ax, bx, x * 2 + 1, mid + 1, r);
}
int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++ ) cin >> a, v[a - 1].push_back(i);
	for(ll i = 0; i < n; i++) {
		cin >> p[i];
	}
	cin >> q;
	bn = (1 << ((ll)log2(m - 1) + 1));
	for(ll i = 0; i < q; i++) {
		cin >> a >> b >> c;
		quer.push_back({c, {a - 1, b - 1}});		
	}
	for(ll i = 0; i < n; i++) midl[q/2].push_back({i, {0, q}});
	while(!done) {
		for(ll i = 0; i < 2 * bn; i++) tour[i] = 0, laz[i] = 0;
		for(ll i = 0; i < q; i++) {

			if(quer[i].second.first > quer[i].second.second) {
//				cout << 0 <<" -> " << quer[i].second.second << " : " << quer[i].first << '\n';
//				cout << quer[i].second.first <<" -> " << m << " : " << quer[i].first << '\n';
				upd(0, quer[i].second.second, quer[i].first);
				upd(quer[i].second.first, m - 1, quer[i].first);
			} else {
//				cout << quer[i].second.first <<" -> " << quer[i].second.second << " : " << quer[i].first << '\n';
				upd(quer[i].second.first, quer[i].second.second, quer[i].first);
			}
//			for(int i = 1; i < 2 * bn; i++) cout << laz[i] << " . ";
//			cout << '\n';
			for(ll j = 0; j < midl[i].size(); j++) {
				ll x = 0;
				for(ll k = 0; k < v[midl[i][j].first].size(); k++) {

					x += query(v[midl[i][j].first][k], v[midl[i][j].first][k]);					
//					cout << x << " . " << v[midl[i][j].first][k] << " . " << midl[i][j].first  << '\n';
				}
//				cout << x << "x\n";
				ll le = midl[i][j].second.first;
				ll re = midl[i][j].second.second;
				ll y = midl[i][j].first;
				ll mid = (le + re)/2;
				if(x < p[y]) {
					le = mid + 1;
				} else {
					re = mid;
				}
				mid = (le + re)/2;
//				cout << "moving " << y << " to " << le << " + " << re << " = " << mid << " " << p[y] << "\n";
				if(le == re) ans[y] = le;
				else {
					nx.push_back({mid, {y, {le, re}}});					
				}				
			}
			while(midl[i].size()) midl[i].pop_back();			
		}
		done = !(nx.size());
		for(ll j = 0; j < nx.size(); j++) midl[nx[j].first].push_back(nx[j].second);
		nx.clear();
	}
	for(ll i = 0; i < n; i++) {
		if(ans[i] == q) cout << "NIE\n";
		else cout << ans[i] + 1 << '\n';
	}
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   37 |  for(int i = 0; i < m; i++ ) cin >> a, v[a - 1].push_back(i);
      |                 ~~^~~

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