Submission #168186

#	Time	Username	Problem	Language	Result	Execution time	Memory
168186		Thuleanx	Meteors (POI11_met)	C++14	100 / 100	2600 ms	37384 KiB

met

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5+7;
int n, m, q;
long long tree[N];
int l[N], r[N];
vector<int> host[N];
int ll[N], rr[N], xx[N];
int need[N];

void add(int v, int x) {
	for (; v < N; v|=v+1)
		tree[v] += x;
}

long long sum(int v) {
	long long ans = 0;
	for (; v >= 0; v = (v&(v+1))-1)
		ans += tree[v];
	return ans;
}

void init() {
	for (int i = 0; i < N; i++)
		tree[i] = 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n>>m;
	for (int i = 0; i < m; i++) {
		int x; cin>>x;
		host[--x].push_back(i);
	}
	for (int i = 0; i < n; i++)
		cin>>need[i];
	cin>>q;
	for (int i = 0; i < n; i++)
		l[i] = 0, r[i] = q-1;
	for (int i = 0; i < q; i++) {
		cin>>ll[i]>>rr[i]>>xx[i];
		ll[i]--; rr[i]--;
	}
	vector<int> h;
	for (int i = 0; i < n; i++)
		h.push_back(i);		
	while (h.size()) {
		init();
		vector<pair<int,int>> tba;		
		while (h.size()) {
			int v = h.back();
			if (l[v] <= r[v])
				tba.push_back({l[v]+r[v]>>1, v});
			h.pop_back();
		}
		sort(begin(tba),end(tba));
		int c = 0;
		for (pair<int,int> p : tba) {
			while (c <= p.first) {
				if (ll[c] <= rr[c]) {
					add(ll[c], xx[c]);
					add(rr[c]+1, -xx[c]);
				} else {
					add(0,xx[c]);
					add(rr[c]+1,-xx[c]);
					add(ll[c], xx[c]);
				}
				c++;					
			}
			int v = p.second;
			long long s = 0;
			for (int i : host[v]) {
				s += sum(i);
				if (s > 1e9) s = 1e9+1;
			}
			if (s < need[v])	l[v] = p.first+1;				
			else 				r[v] = p.first-1;
			if (l[v] <= r[v])
				h.push_back(v);
		}
	}
	stringstream ss;
	for (int i = 0; i < n; i++) {
		if (l[i] == q)
			ss << "NIE" << endl;
		else
			ss << l[i]+1 << endl;
	}
	cout << ss.str();


	return 0;
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:56:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     tba.push_back({l[v]+r[v]>>1, v});
                    ~~~~^~~~~

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