//çalışan kazanır//
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define pb push_back
#define S second
#define F first
#define all(x) x.begin(),x.end()
#define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0)
int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
const int N = 4e5 + 1;
const int INF = 2e18 + 1;
const int MOD = 1e9 + 7;
const int MODD = 1070234587ll;
const double eps = 0.0001;
//const int p = 87;
int n, m, o[N], p[N], q, l[N], r[N], a[N];
vector <int> pos[N];
int t[N*4], mod[N*4];
void push (int v, int tl, int tr) {
if (mod[v] && tl != tr) {
mod[v + v] += mod[v], mod[v + v + 1] += mod[v];
t[v + v] += mod[v], t[v + v + 1] += mod[v];
mod[v] = 0;
}
return;
}
void upd (int v, int tl, int tr, int l, int r, int val) {
push (v, tl, tr);
if (tr < l || r < tl) return;
if (l <= tl && tr <= r) {
t[v] += val;
mod[v] += val;
push (v, tl, tr);
return;
}
int mid = (tl + tr) >> 1;
upd (v + v, tl, mid, l, r, val), upd (v + v + 1, mid + 1, tr, l, r, val);
t[v] = max (t[v + v], t[v + v + 1]);
return;
}
void cl (int v, int tl, int tr) {
t[v] = mod[v] = 0;
if (tl == tr) return;
int mid = (tl + tr) >> 1;
cl (v + v, tl, mid), cl (v + v + 1, mid + 1, tr);
return;
}
int get (int v, int tl, int tr, int pos) {
push (v, tl, tr);
if (tl == tr) return t[v];
int mid = (tl + tr) >> 1;
if (pos <= mid) return get (v + v, tl, mid, pos);
return get (v + v + 1, mid + 1, tr, pos);
}
int check (int x, int idx) {
for (int i = 1; i <= x; ++ i) {
if (l[i] <= r[i]) upd (1, 1, m, l[i], r[i], a[i]);
else upd (1, 1, m, 1, r[i], a[i]), upd (1, 1, m, l[i], m, a[i]);
}
int sum = 0;
for (auto i: pos[idx]) {
// cout << i << " --> " << get (1, 1, m, i) << '\n';
sum += get (1, 1, m, i);
}
cl(1, 1, m);
// cout << x << ' ' << idx << " ==> " << sum << ' ' << p[idx] << '\n';
return (sum >= p[idx]);
}
void solution () {
cin >> n >> m;
for (int i = 1; i <= m; ++ i) {
cin >> o[i];
pos[o[i]].pb (i);
}
for (int i = 1; i <= n; ++ i) cin >> p[i];
cin >> q;
for (int i = 1; i <= q; ++ i) cin >> l[i] >> r[i] >> a[i];
for (int i = 1; i <= n; ++ i) {
int L = 0, R = q, rs = -1;
while (L <= R) {
int mid = (L + R) >> 1;
if (check (mid, i)) R = mid - 1, rs = mid;
else L = mid + 1;
}
if (rs == -1) cout << "NIE\n";
else cout << rs << '\n';
}
return;
}
signed main() {
YOSIK();
// srand (time(0));
// freopen ("E.in", "r", stdin);
// freopen ("E.out", "w", stdout);
int TT = 1;// cin >> TT;
for (int i = 1; i <= TT; ++ i) {
// cout << "Case " << i << ": ";
solution ();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
216 ms |
20996 KB |
Output is correct |
| 2 |
Correct |
1239 ms |
20992 KB |
Output is correct |
| 3 |
Correct |
324 ms |
20992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
251 ms |
20992 KB |
Output is correct |
| 2 |
Correct |
109 ms |
21000 KB |
Output is correct |
| 3 |
Correct |
1345 ms |
21076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6013 ms |
22360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6012 ms |
23640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6053 ms |
22616 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6019 ms |
22488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6015 ms |
48984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6006 ms |
48708 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
