#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[k + 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 |
3 ms |
336 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
4 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
4 ms |
460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
308 ms |
4996 KB |
Output is correct |
| 2 |
Correct |
361 ms |
6708 KB |
Output is correct |
| 3 |
Correct |
357 ms |
5968 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
350 ms |
5540 KB |
Output is correct |
| 2 |
Correct |
318 ms |
5596 KB |
Output is correct |
| 3 |
Correct |
373 ms |
6832 KB |
Output is correct |
| 4 |
Correct |
78 ms |
4000 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
150 ms |
5156 KB |
Output is correct |
| 2 |
Correct |
260 ms |
6692 KB |
Output is correct |
| 3 |
Correct |
140 ms |
2796 KB |
Output is correct |
| 4 |
Correct |
331 ms |
6372 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
308 ms |
4620 KB |
Output is correct |
| 2 |
Correct |
364 ms |
5608 KB |
Output is correct |
| 3 |
Correct |
295 ms |
4912 KB |
Output is correct |
| 4 |
Correct |
401 ms |
7208 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3754 ms |
37872 KB |
Output is correct |
| 2 |
Incorrect |
1626 ms |
27556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3501 ms |
36600 KB |
Output is correct |
| 2 |
Incorrect |
1092 ms |
27424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
