oj.uz

답안 #347725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
347725 2021-01-13T10:45:08 Z lovro_nidogon1 Meteors (POI11_met) C++14
74 / 100
 6000 ms 55516 KB 
#include<bits/stdc++.h>
#define breturn return
#define ll long long
using namespace std;
const int maxn = 300001;
ll n, m, o[maxn], p[maxn], a, b, c, q, bn, tour[1048600], laz[1048600], ans[maxn]; 
vector<pair<ll, pair<ll, ll> > > midl[maxn], quer;
vector<pair<ll, pair<ll, pair<ll, ll> > > > nx;
vector<ll> v[maxn];
bool done; 
void upd(ll ax, ll bx, ll val, ll x = 1, ll l = 0, ll r = bn - 1) {	
	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 + (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[(int)(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) {
				upd(0, quer[i].second.second, quer[i].first);
				upd(quer[i].second.first, m - 1, quer[i].first);
			} else upd(quer[i].second.first, quer[i].second.second, quer[i].first);			
			for(ll j = 0; j < midl[i].size(); j++) {				
				ll y = midl[i][j].first;
				unsigned ll x = 0;
				for(ll k = 0; k < v[y].size(); k++) {
					x += query(v[y][k], v[y][k]);									
					if(x >= 1e9) break;
				}	
				ll le = midl[i][j].second.first;
				ll re = midl[i][j].second.second;
				ll mid = (le + re)/2;
				if(x < p[y]) le = mid + 1;
				else re = mid;				
				mid = (le + re)/2;
				if(le == re) ans[y] = le;
				else nx.push_back({mid, {y, {le, re}}});													
			}
			midl[i].clear();
			midl[i].shrink_to_fit();			
		}
		done = !(nx.size());
		for(ll j = 0; j < nx.size(); j++) midl[nx[j].first].push_back(nx[j].second);
		nx.clear();
		nx.shrink_to_fit();

	}
	for(ll i = 0; i < n; i++) {
		if(ans[i] == q) cout << "NIE\n";
		else cout << ans[i] + 1 << '\n';
	}
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:52:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for(ll j = 0; j < midl[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~
met.cpp:55:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(ll k = 0; k < v[y].size(); k++) {
      |                   ~~^~~~~~~~~~~~~
met.cpp:62:10: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   62 |     if(x < p[y]) le = mid + 1;
      |        ~~^~~~~~
met.cpp:72:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, std::pair<long long int, long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(ll j = 0; j < nx.size(); j++) midl[nx[j].first].push_back(nx[j].second);
      |                 ~~^~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14572 KB Output is correct
2 Correct 14 ms 14572 KB Output is correct
3 Correct 15 ms 14572 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14572 KB Output is correct
2 Correct 14 ms 14572 KB Output is correct
3 Correct 14 ms 14572 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 468 ms 18956 KB Output is correct
2 Correct 631 ms 21508 KB Output is correct
3 Correct 596 ms 20356 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 557 ms 19940 KB Output is correct
2 Correct 658 ms 19912 KB Output is correct
3 Correct 646 ms 21740 KB Output is correct
4 Correct 184 ms 19376 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 19168 KB Output is correct
2 Correct 447 ms 22120 KB Output is correct
3 Correct 223 ms 16100 KB Output is correct
4 Correct 562 ms 20836 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 18400 KB Output is correct
2 Correct 490 ms 19932 KB Output is correct
3 Correct 482 ms 18528 KB Output is correct
4 Correct 619 ms 22192 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6025 ms 55516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6061 ms 54636 KB Time limit exceeded
2 Halted 0 ms 0 KB -