# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
496577 |
2021-12-21T14:55:03 Z |
Ziel |
Meteors (POI11_met) |
C++17 |
|
6000 ms |
23096 KB |
/**
* LES GREATEABLES BRO TEAM
**/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
const bool FLAG = false;
void setIO(const string &f = "");
const int N = 3e5 + 13;
ll bit[N], prev_bit[N];
int n, m;
void upd(int x, ll v) {
for (; x <= m + 1; x |= (x + 1))
bit[x] += v;
}
ll get(int x) {
ll res = 0;
for (; x > 0; x = (x & (x + 1)) - 1)
res += bit[x];
return res;
}
void prev_upd(int x, ll v) {
for (; x <= m + 1; x |= (x + 1))
prev_bit[x] += v;
}
ll prev_get(int x) {
ll res = 0;
for (; x > 0; x = (x & (x + 1)) - 1)
res += prev_bit[x];
return res;
}
void solve() {
cin >> n >> m;
vector<int> o(m + 1);
vector<vector<int>> occ(n + 1);
for (int i = 1; i <= m; i++) {
cin >> o[i];
occ[o[i]].push_back(i);
}
vector<int> p(n + 1);
for (int i = 1; i <= n; i++)
cin >> p[i];
int q;
cin >> q;
int cnt_rep = 0;
vector<int> l(q + 1), r(q + 1), a(q + 1), ans(n + 1, -1);
for (int rep = 1; rep <= q; rep++) {
cin >> l[rep] >> r[rep] >> a[rep];
if (l[rep] <= r[rep]) {
upd(l[rep], a[rep]);
upd(r[rep] + 1, -a[rep]);
} else {
upd(l[rep], a[rep]);
upd(m + 1, -a[rep]);
upd(1, a[rep]);
upd(r[rep] + 1, -a[rep]);
}
cnt_rep++;
if (cnt_rep >= 500) {
vector<int> cur_p(n + 1);
for (int i = 1; i <= m; i++)
cur_p[o[i]] += get(i);
set<int> temp;
for (int i = 1; i <= n; i++) {
if (cur_p[i] >= p[i])
temp.insert(i);
}
for (int i = rep - 500 + 1; i <= rep; i++) {
if (l[i] <= r[i]) {
prev_upd(l[i], a[i]);
prev_upd(r[i] + 1, -a[i]);
} else {
prev_upd(l[i], a[i]);
prev_upd(m + 1, -a[i]);
prev_upd(1, a[i]);
prev_upd(r[i] + 1, -a[i]);
}
if (sz(temp)) {
vector<int> del;
for (int x: temp) {
int cur = 0;
for (int y: occ[x]) {
cur += prev_get(y);
}
if (cur >= p[x]) {
ans[x] = i;
del.push_back(x);
}
}
for (int x: del)
temp.erase(x);
}
}
cnt_rep = 0;
}
}
vector<int> cur_p(n + 1);
for (int i = 1; i <= m; i++)
cur_p[o[i]] += get(i);
set<int> temp;
for (int i = 1; i <= n; i++) {
if (cur_p[i] >= p[i])
temp.insert(i);
}
for (int i = n - cnt_rep + 1; i <= n; i++) {
if (l[i] <= r[i]) {
prev_upd(l[i], a[i]);
prev_upd(r[i] + 1, -a[i]);
} else {
prev_upd(l[i], a[i]);
prev_upd(m + 1, -a[i]);
prev_upd(1, a[i]);
prev_upd(r[i] + 1, -a[i]);
}
if (sz(temp)) {
vector<int> del;
for (int x: temp) {
int cur = 0;
for (int y: occ[x]) {
cur += prev_get(y);
}
if (cur >= p[x]) {
ans[x] = i;
del.push_back(x);
}
}
for (int x: del)
temp.erase(x);
}
}
for (int i = 1; i <= n; i++) {
if (ans[i] == -1)
cout << "NIE\n";
else
cout << ans[i] << '\n';
}
}
signed main() {
setIO();
int tt = 1;
if (FLAG) {
cin >> tt;
}
while (tt--) {
solve();
}
return 0;
}
void setIO(const string &f) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen((f + ".in").c_str(), "r")) {
freopen((f + ".in").c_str(), "r", stdin);
freopen((f + ".out").c_str(), "w", stdout);
}
}
Compilation message
met.cpp: In function 'void setIO(const string&)':
met.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
174 | freopen((f + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
175 | freopen((f + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
328 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
161 ms |
3132 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
395 ms |
3980 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
252 ms |
3420 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
433 ms |
3016 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6068 ms |
23096 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6052 ms |
22040 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |