oj.uz

Submission #168186

# Submission time Handle Problem Language Result Execution time Memory
168186 2019-12-11T20:45:09 Z Thuleanx Meteors (POI11_met) C++14
100 / 100
 2600 ms 37384 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9848 KB Output is correct
2 Correct 14 ms 9848 KB Output is correct
3 Correct 13 ms 9808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9848 KB Output is correct
2 Correct 13 ms 9852 KB Output is correct
3 Correct 14 ms 9848 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 10872 KB Output is correct
2 Correct 211 ms 12040 KB Output is correct
3 Correct 151 ms 11408 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 11128 KB Output is correct
2 Correct 170 ms 11196 KB Output is correct
3 Correct 220 ms 12012 KB Output is correct
4 Correct 53 ms 10908 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 10980 KB Output is correct
2 Correct 216 ms 12068 KB Output is correct
3 Correct 67 ms 10360 KB Output is correct
4 Correct 156 ms 11752 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10616 KB Output is correct
2 Correct 183 ms 11220 KB Output is correct
3 Correct 119 ms 10872 KB Output is correct
4 Correct 200 ms 12168 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1489 ms 21036 KB Output is correct
2 Correct 258 ms 14576 KB Output is correct
3 Correct 439 ms 15140 KB Output is correct
4 Correct 2214 ms 35444 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1404 ms 20548 KB Output is correct
2 Correct 702 ms 14584 KB Output is correct
3 Correct 106 ms 15612 KB Output is correct
4 Correct 2600 ms 37384 KB Output is correct