| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 347729 |
2021-01-13T10:46:29 Z |
mkisic |
Meteors (POI11_met) |
C++14 |
|
6000 ms |
56224 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);
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14600 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14572 KB |
Output is correct |
| 3 |
Correct |
16 ms |
14572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
473 ms |
18916 KB |
Output is correct |
| 2 |
Correct |
625 ms |
21636 KB |
Output is correct |
| 3 |
Correct |
571 ms |
20320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
552 ms |
20196 KB |
Output is correct |
| 2 |
Correct |
578 ms |
19940 KB |
Output is correct |
| 3 |
Correct |
652 ms |
21688 KB |
Output is correct |
| 4 |
Correct |
189 ms |
19248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
314 ms |
19168 KB |
Output is correct |
| 2 |
Correct |
502 ms |
22056 KB |
Output is correct |
| 3 |
Correct |
207 ms |
16100 KB |
Output is correct |
| 4 |
Correct |
655 ms |
20904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
528 ms |
18360 KB |
Output is correct |
| 2 |
Correct |
515 ms |
19928 KB |
Output is correct |
| 3 |
Correct |
485 ms |
18528 KB |
Output is correct |
| 4 |
Correct |
620 ms |
21948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6088 ms |
56224 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6046 ms |
54872 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
