## Submission #202242

# Submission time Handle Problem Language Result Execution time Memory
202242 2020-02-14T13:36:03 Z himyu Meteors (POI11_met) C++17
24 / 100
231 ms 65536 KB
```#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

template <class T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

class Node {
public:
i64 v;
int l, r;

Node() {
v = 0;
l = r = 0;
}

Node(i64 _v) {
v = _v;
l = r = 0;
}

Node(i64 _v, int _l, int _r) {
v = _v;
l = _l, r = _r;
}
};

namespace PST {
Node seg[2101010];
int sz = 0;

vector<int> v;

int init(int s, int e) {
if (s == e)
seg[sz] = Node(0);
else
seg[sz] = Node(0, init(s, (s + e) / 2), init((s + e) / 2 + 1, e));
return sz++;
}

int update(int s, int e, int h, const int t, const i64 d) {
if (t < s || e < t) return h;

if (s == e)
seg[sz] = Node(seg[h].v + d);
else {
auto l = update(s, (s + e) / 2, seg[h].l, t, d);
auto r = update((s + e) / 2 + 1, e, seg[h].r, t, d);
seg[sz] = Node(seg[l].v + seg[r].v, l, r);
}

return sz++;
}

i64 query(int s, int e, int h, const int l, const int r) {
if (r < s || e < l)
return 0;
else if (l <= s && e <= r)
return seg[h].v;
else
return query(s, (s + e) / 2, seg[h].l, l, r) +
query((s + e) / 2 + 1, e, seg[h].r, l, r);
}
}  // namespace PST

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

int N, M;
cin >> N >> M;

vector<vector<int>> team(N + 1);
for (int i = 1; i <= M; i++) {
int k;
cin >> k;
team[k].emplace_back(i);
}

vector<i64> goal(N + 1);
for (int i = 1; i <= N; i++) cin >> goal[i];

PST::v.emplace_back(PST::init(1, M));

int Q;
cin >> Q;

for (int i = 1; i <= Q; i++) {
int l, r;
i64 d;
cin >> l >> r >> d;

if (l <= r) {
PST::v.emplace_back(PST::update(1, M, PST::v[i - 1], l, d));
if (r != M) PST::v[i] = PST::update(1, M, PST::v[i], r + 1, -d);
} else {
swap(l, r);
PST::v.emplace_back(PST::update(1, M, PST::v[i - 1], 1, d));
PST::v[i] = PST::update(1, M, PST::v[i], l + 1, -d);
PST::v[i] = PST::update(1, M, PST::v[i], r, d);
}
}

for (int i = 1; i <= N; i++) {
int s = 1, e = Q + 1;
while (s < e) {
int m = (s + e) / 2;
auto root = PST::v[m];

i64 q = 0;
for (auto el : team[i]) q += PST::query(1, M, root, 1, el);

if (q < goal[i])
s = m + 1;
else
e = m;
}

if (s == Q + 1)
cout << "NIE";
else
cout << s;
cout << '\n';
}

return 0;
}```

#### Subtask #1 12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33272 KB Output is correct
2 Correct 24 ms 33272 KB Output is correct
3 Correct 25 ms 33400 KB Output is correct

#### Subtask #2 12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33272 KB Output is correct
2 Correct 25 ms 33272 KB Output is correct
3 Correct 24 ms 33272 KB Output is correct

#### Subtask #3 0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 34980 KB Output is correct
2 Runtime error 155 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

#### Subtask #4 0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

#### Subtask #5 0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 34936 KB Output is correct
2 Runtime error 113 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

#### Subtask #6 0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

#### Subtask #7 0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 231 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

#### Subtask #8 0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 221 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -