| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 548547 |
2022-04-13T18:33:59 Z |
2fat2code |
Meteors (POI11_met) |
C++17 |
|
1246 ms |
42736 KB |
#include<bits/stdc++.h>
using namespace std;
const int pot = 512 * 1024;
long long tr[2*pot];
vector<int> properties[pot];
int need[pot];
int ans[pot];
int from[pot], to[pot], val[pot];
void tree_add(int low, int high, int v) {
assert(low <= high);
low += pot;
high += pot;
tr[low] += v;
if(low != high) tr[high] += v;
while(low + 1 < high) {
if(low % 2 == 0) tr[low+1] += v;
if(high % 2 == 1) tr[high-1] += v;
low /= 2;
high /= 2;
}
}
void tree_add(int i_q, int multiplier) {
int v = val[i_q] * multiplier;
if(from[i_q] <= to[i_q])
tree_add(from[i_q], to[i_q], v);
else {
tree_add(from[i_q], pot - 1, v);
tree_add(0, to[i_q], v);
}
}
long long tree_get(int where) {
long long s = 0;
for(int x = pot + where; x >= 1; x /= 2)
s += tr[x];
return s;
}
void rec(int low, int high, vector<int> & owners, int & act_tree) {
if(owners.empty()) return;
int mid = (low + high) / 2;
while(act_tree < mid)
tree_add(++act_tree, 1);
while(act_tree > mid)
tree_add(act_tree--, -1);
vector<int> left_owners;
vector<int> right_owners;
for(int who : owners) {
long long his_value = 0;
for(int where : properties[who]) {
his_value += tree_get(where);
if(his_value >= need[who]) break;
}
if(his_value >= need[who]) {
left_owners.push_back(who);
ans[who] = high;
}
else
right_owners.push_back(who);
}
owners.clear(); // thanks to this line the memory is O(n), not O(n log(n))
if(low < high) {
rec(low, mid, left_owners, act_tree);
rec(mid + 1, high, right_owners, act_tree);
}
}
int main() {
int n, len;
scanf("%d%d", &n, &len);
for(int where = 1; where <= len; ++where) {
int who;
scanf("%d", &who);
properties[who].push_back(where);
}
for(int who = 1; who <= n; ++who)
scanf("%d", &need[who]);
int q;
scanf("%d", &q);
for(int day = 1; day <= q; ++day)
scanf("%d%d%d", &from[day], &to[day], &val[day]);
vector<int> owners;
for(int who = 1; who <= n; ++who)
owners.push_back(who);
int act_tree = 0;
rec(1, q, owners, act_tree);
for(int who = 1; who <= n; ++who) {
if(ans[who]) printf("%d\n", ans[who]);
else puts("NIE");
}
return 0;
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d%d", &n, &len);
| ~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d", &who);
| ~~~~~^~~~~~~~~~~~
met.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d", &need[who]);
| ~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
met.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d%d%d", &from[day], &to[day], &val[day]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12768 KB |
Output is correct |
| 3 |
Correct |
8 ms |
12628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12656 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
14744 KB |
Output is correct |
| 2 |
Correct |
91 ms |
16832 KB |
Output is correct |
| 3 |
Correct |
99 ms |
14992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
14772 KB |
Output is correct |
| 2 |
Correct |
102 ms |
14720 KB |
Output is correct |
| 3 |
Correct |
70 ms |
16128 KB |
Output is correct |
| 4 |
Correct |
33 ms |
14820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
14652 KB |
Output is correct |
| 2 |
Correct |
94 ms |
16236 KB |
Output is correct |
| 3 |
Correct |
32 ms |
13308 KB |
Output is correct |
| 4 |
Correct |
119 ms |
15136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
14396 KB |
Output is correct |
| 2 |
Correct |
97 ms |
14796 KB |
Output is correct |
| 3 |
Correct |
70 ms |
14416 KB |
Output is correct |
| 4 |
Correct |
118 ms |
15740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
569 ms |
30704 KB |
Output is correct |
| 2 |
Correct |
143 ms |
19916 KB |
Output is correct |
| 3 |
Correct |
153 ms |
18016 KB |
Output is correct |
| 4 |
Correct |
1246 ms |
40880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
534 ms |
28860 KB |
Output is correct |
| 2 |
Correct |
173 ms |
20928 KB |
Output is correct |
| 3 |
Correct |
74 ms |
18440 KB |
Output is correct |
| 4 |
Correct |
1217 ms |
42736 KB |
Output is correct |
