oj.uz

Submission #168184

# Submission time Handle Problem Language Result Execution time Memory
168184 2019-12-11T20:25:12 Z Thuleanx Meteors (POI11_met) C++14
74 / 100
 1424 ms 28884 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();
			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 < 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:23: 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 9976 KB Output is correct
2 Correct 13 ms 9848 KB Output is correct
3 Correct 13 ms 9848 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 14 ms 9848 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 109 ms 11768 KB Output is correct
2 Correct 207 ms 13104 KB Output is correct
3 Correct 150 ms 12560 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 12280 KB Output is correct
2 Correct 180 ms 12360 KB Output is correct
3 Correct 221 ms 13212 KB Output is correct
4 Correct 54 ms 11512 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 11792 KB Output is correct
2 Correct 214 ms 13236 KB Output is correct
3 Correct 68 ms 11012 KB Output is correct
4 Correct 156 ms 12824 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 11744 KB Output is correct
2 Correct 182 ms 12716 KB Output is correct
3 Correct 117 ms 11768 KB Output is correct
4 Correct 199 ms 13480 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1424 ms 28884 KB Output is correct
2 Incorrect 928 ms 22492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1378 ms 28076 KB Output is correct
2 Incorrect 826 ms 21108 KB Output isn't correct
3 Halted 0 ms 0 KB -