| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 862325 |
2023-10-18T04:10:09 Z |
sleepntsheep |
Meteors (POI11_met) |
C++17 |
|
1206 ms |
33036 KB |
#include <bits/stdc++.h>
template <class T>
struct BIT
{
int n;
std::vector<T> a;
BIT(int m) : n(1+m), a(2+m) {}
void inc(int p, T x) { for (++p; p <= n; p+=p&-p) a[p] += x; }
auto qry(int p, T z = 0) { for (++p; p; p-=p&-p) z+=a[p]; return z;}
};
int main()
{
int n_state, n_sector, n_meteor;
scanf("%d%d", &n_state, &n_sector);
std::vector<std::vector<int>> states(n_state);
std::vector<int> sample(n_state), ans(n_state, -1);
for (int owner, i = 1; i <= n_sector; ++i)
scanf("%d", &owner), states[--owner].push_back(i);
for (int &x : sample) scanf("%d", &x);
scanf("%d", &n_meteor);
std::vector<std::tuple<int, int, int>> meteors(n_meteor);
for (auto &[l, r, a] : meteors) scanf("%d%d%d", &l, &r, &a);
BIT<int64_t> fw(n_sector + 20000);
std::function<void(int, int, std::vector<int>&)> parallel_bs = [&](int l, int r, std::vector<int> &candi) {
if (candi.empty()) return;
auto m = l + (r-l)/2;
for (int i = l; i <= m; ++i) {
auto [ml, mr, ma] = meteors[i];
fw.inc(ml, ma);
fw.inc(mr + 1, -ma);
if (ml > mr) fw.inc(1, ma), fw.inc(n_sector + 1, -ma);
}
std::vector<int> ok, not_ok;
for (auto c : candi) {
uint64_t sum = 0;
for (auto st : states[c]) sum += fw.qry(st);
if (sum >= sample[c]) ok.push_back(c), ans[c] = m;
else not_ok.push_back(c), sample[c] -= sum;
}
for (int i = l; i <= m; ++i) {
auto [ml, mr, ma] = meteors[i];
ma *= -1;
fw.inc(ml, ma);
fw.inc(mr + 1, -ma);
if (ml > mr) fw.inc(1, ma), fw.inc(n_sector + 1, -ma);
}
if (l != r)
{
parallel_bs(l, m, ok); std::vector<int>().swap(ok);
parallel_bs(m+1, r, not_ok); std::vector<int>().swap(not_ok);
}
};
std::vector<int> all(n_state);
std::iota(all.begin(), all.end(), 0);
parallel_bs(0, n_meteor - 1, all);
for (int i = 0; i < n_state; ++i)
{
if (ans[i] == -1) puts("NIE");
else printf("%d\n", ans[i] + 1);
}
return 0;
}
Compilation message
met.cpp: In lambda function:
met.cpp:47:21: warning: comparison of integer expressions of different signedness: 'uint64_t' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
47 | if (sum >= sample[c]) ok.push_back(c), ans[c] = m;
met.cpp: In function 'int main()':
met.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%d%d", &n_state, &n_sector);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%d", &owner), states[--owner].push_back(i);
| ~~~~~^~~~~~~~~~~~~~
met.cpp:23:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | for (int &x : sample) scanf("%d", &x);
| ~~~~~^~~~~~~~~~
met.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | scanf("%d", &n_meteor);
| ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:27:42: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | for (auto &[l, r, a] : meteors) scanf("%d%d%d", &l, &r, &a);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
3004 KB |
Output is correct |
| 2 |
Correct |
68 ms |
5452 KB |
Output is correct |
| 3 |
Correct |
73 ms |
3408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
3188 KB |
Output is correct |
| 2 |
Correct |
74 ms |
3160 KB |
Output is correct |
| 3 |
Correct |
51 ms |
4812 KB |
Output is correct |
| 4 |
Correct |
20 ms |
2896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
2940 KB |
Output is correct |
| 2 |
Correct |
78 ms |
5512 KB |
Output is correct |
| 3 |
Correct |
21 ms |
1628 KB |
Output is correct |
| 4 |
Correct |
70 ms |
3688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
81 ms |
3156 KB |
Output is correct |
| 3 |
Correct |
38 ms |
2744 KB |
Output is correct |
| 4 |
Correct |
92 ms |
4768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
359 ms |
22648 KB |
Output is correct |
| 2 |
Correct |
158 ms |
11732 KB |
Output is correct |
| 3 |
Correct |
130 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
1193 ms |
26460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
373 ms |
20444 KB |
Output is correct |
| 2 |
Correct |
242 ms |
11092 KB |
Output is correct |
| 3 |
Correct |
55 ms |
4896 KB |
Output is correct |
| 4 |
Correct |
1206 ms |
33036 KB |
Output is correct |
