oj.uz

Submission #168185

# Submission time Handle Problem Language Result Execution time Memory
168185 2019-12-11T20:37:01 Z Thuleanx Meteors (POI11_met) C++14
74 / 100
 1440 ms 21092 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:55: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 9720 KB Output is correct
2 Correct 13 ms 9848 KB Output is correct
3 Correct 13 ms 9724 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 10920 KB Output is correct
2 Correct 208 ms 11872 KB Output is correct
3 Correct 150 ms 11400 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 11128 KB Output is correct
2 Correct 168 ms 11216 KB Output is correct
3 Correct 222 ms 12072 KB Output is correct
4 Correct 53 ms 10960 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 11000 KB Output is correct
2 Correct 214 ms 12040 KB Output is correct
3 Correct 67 ms 10360 KB Output is correct
4 Correct 157 ms 11708 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 10616 KB Output is correct
2 Correct 181 ms 11224 KB Output is correct
3 Correct 117 ms 10872 KB Output is correct
4 Correct 201 ms 12180 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 21092 KB Output is correct
2 Incorrect 968 ms 14740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1387 ms 20452 KB Output is correct
2 Incorrect 800 ms 14708 KB Output isn't correct
3 Halted 0 ms 0 KB -