#include<bits/stdc++.h>
/*
#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
*/
//01001101 01100001 01101011 01101000 01100001 01100111 01100001 01111001
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define pb push_back
#define sz(a) a.size()
#define nl '\n'
#define popb pop_back()
#define ld double
#define ull unsigned long long
#define ff first
#define ss second
#define fix fixed << setprecision
#define pii pair<int, int>
#define E exit (0)
#define int long long
const int inf = 1e15, N = 3e5 + 5, mod = 998244353;
vector<pii> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int t[4 * N], ans[N];
void build(int u, int tl, int tr) {
t[u] = 0;
if (tl == tr) {
return;
}
int mid = (tl + tr) / 2;
build(u * 2, tl, mid);
build(u * 2 + 1, mid + 1, tr);
}
void update(int u, int tl, int tr, int l, int r, int val) {
if (tl >= l && tr <= r) {
t[u] += val;
return;
}
if (tl > r || tr < l) return;
int mid = (tl + tr) / 2;
update(u * 2, tl, mid, l, r, val);
update(u * 2 + 1, mid + 1, tr, l, r, val);
}
int get(int u, int tl, int tr, int pos) {
if (tl == tr) return t[u];
int mid = (tl + tr) / 2;
if (pos <= mid) return get(u * 2, tl, mid, pos) + t[u];
return get(u * 2 + 1, mid + 1, tr, pos) + t[u];
}
main() {
//freopen("triangles.in", "r", stdin);
//freopen("triangles.out", "w", stdout);
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
int n, m;
cin >> n >> m;
int a[m + 1], b[n + 1];
vector<int> h[n + 1];
for (int i = 1; i <= m; i++) {
cin >> a[i];
h[a[i]].pb(i);
}
for (int i = 1; i <= n; i++) cin >> b[i];
int k;
cin >> k;
int l[k + 1], r[k + 1], x[k + 1];
for (int i = 1; i <= k; i++) {
cin >> l[i] >> r[i] >> x[i];
}
vector<pii> s(n + 1, {1, k});
while (true) {
build(1, 1, m);
vector<int> c[m + 1];
bool ok = 1;
for (int i = 1; i <= n; i++) {
int tl = s[i].ff, tr = s[i].ss, mid = (tl + tr) / 2;
if (tl > tr) {
continue;
}
ok = 0;
c[mid].pb(i);
}
if (ok) break;
for (int i = 1; i <= k; i++) {
if (l[i] <= r[i]) update(1, 1, m, l[i], r[i], x[i]);
else {
update(1, 1, m, 1, r[i], x[i]);
update(1, 1, m, l[i], m, x[i]);
}
for (auto e: c[i]) {
int sum = 0;
for (auto d: h[e]) {
sum += get(1, 1, m, d);
}
if (sum >= b[e]) {
s[e].ss = i - 1;
ans[e] = i;
}else {
s[e].ff = i + 1;
}
}
}
}
for (int i = 1; i <= n; i++) {
if (!ans[i]) {
cout << "NIE" << nl;
continue;
}
cout << ans[i] << nl;
}
}
Compilation message
met.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
65 | main() {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
324 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
4 ms |
440 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
332 KB |
Output is correct |
| 2 |
Correct |
4 ms |
320 KB |
Output is correct |
| 3 |
Correct |
4 ms |
460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
304 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
406 ms |
6780 KB |
Output is correct |
| 3 |
Correct |
414 ms |
5900 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
334 ms |
5624 KB |
Output is correct |
| 2 |
Correct |
349 ms |
5564 KB |
Output is correct |
| 3 |
Correct |
364 ms |
6892 KB |
Output is correct |
| 4 |
Correct |
87 ms |
5004 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
164 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
244 ms |
6792 KB |
Output is correct |
| 3 |
Runtime error |
11 ms |
3012 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
309 ms |
4688 KB |
Output is correct |
| 2 |
Correct |
316 ms |
5540 KB |
Output is correct |
| 3 |
Correct |
302 ms |
4916 KB |
Output is correct |
| 4 |
Correct |
420 ms |
7044 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3686 ms |
38000 KB |
Output is correct |
| 2 |
Incorrect |
1735 ms |
27724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3428 ms |
36716 KB |
Output is correct |
| 2 |
Incorrect |
1164 ms |
27612 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
