//ç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),cout.tie(0)
int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
const int N = 3e5 + 15;
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], ans[N];
pair <int, int> brd[N];
vector <int> pos[N], MID[N];
long long t[N*4], mod[N*4];
void upd (int v, int tl, int tr, int ql, int qr, int val) {
if (tr < ql || qr < tl) return;
if (ql <= tl && tr <= qr) {
t[v] += val;
return;
}
int mid = (tl + tr) >> 1;
upd (v + v, tl, mid, ql, qr, val), upd (v + v + 1, mid + 1, tr, ql, qr, val);
return;
}
long long get (int v, int tl, int tr, int pos) {
if (tl == tr) return t[v];
int mid = (tl + tr) >> 1;
if (pos <= mid) return (t[v] + get (v + v, tl, mid, pos));
return (t[v] + get (v + v + 1, mid + 1, tr, pos));
}
void cl (int v, int tl, int tr) {
t[v] = 0;
if (tl == tr) return;
int mid = (tl + tr) >> 1;
cl (v + v, tl, mid), cl (v + v + 1, mid + 1, tr);
return;
}
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) brd[i] = make_pair (1, q), ans[i] = -1;
long long sum = 0, ok = 1;
while (ok) {
ok = 0;
for (int i = 1; i <= n; ++ i) {
if (brd[i].F > brd[i].S) continue;
MID[(brd[i].F + brd[i].S) >> 1].pb (i);
}
for (int mid = 1; mid <= q; ++ mid) {
if (l[mid] <= r[mid]) upd (1, 1, m, l[mid], r[mid], a[mid]);
else {
upd (1, 1, m, 1, r[mid], a[mid]);
upd (1, 1, m, l[mid], m, a[mid]);
}
for (auto i: MID[mid]) {
sum = 0, ok = 1;
for (auto j: pos[i]) {
sum += get (1, 1, m, j);
if (sum >= p[i]) break;
}
if (sum >= p[i]) brd[i].S = mid - 1, ans[i] = mid;
else brd[i].F = mid + 1;
}
MID[mid].clear();
}
memset (t, 0, sizeof(t));
}
for (int i = 1; i <= n; ++ i) {
if (ans[i] == -1) cout << "NIE\n";
else cout << ans[i] << '\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;
}
Compilation message
met.cpp:16:22: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
16 | const int INF = 2e18 + 1;
| ~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
31064 KB |
Output is correct |
| 2 |
Correct |
9 ms |
31288 KB |
Output is correct |
| 3 |
Correct |
9 ms |
31068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
31068 KB |
Output is correct |
| 2 |
Correct |
8 ms |
31172 KB |
Output is correct |
| 3 |
Correct |
9 ms |
31324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
228 ms |
31960 KB |
Output is correct |
| 2 |
Correct |
304 ms |
35896 KB |
Output is correct |
| 3 |
Correct |
284 ms |
33364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
273 ms |
32984 KB |
Output is correct |
| 2 |
Correct |
296 ms |
33040 KB |
Output is correct |
| 3 |
Correct |
293 ms |
35828 KB |
Output is correct |
| 4 |
Correct |
58 ms |
32860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
32900 KB |
Output is correct |
| 2 |
Correct |
183 ms |
36336 KB |
Output is correct |
| 3 |
Correct |
130 ms |
31256 KB |
Output is correct |
| 4 |
Correct |
277 ms |
33888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
31576 KB |
Output is correct |
| 2 |
Correct |
240 ms |
32852 KB |
Output is correct |
| 3 |
Correct |
259 ms |
32152 KB |
Output is correct |
| 4 |
Correct |
291 ms |
36960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2448 ms |
46944 KB |
Output is correct |
| 2 |
Correct |
921 ms |
33628 KB |
Output is correct |
| 3 |
Correct |
692 ms |
31552 KB |
Output is correct |
| 4 |
Correct |
3491 ms |
65536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2439 ms |
45780 KB |
Output is correct |
| 2 |
Correct |
744 ms |
33756 KB |
Output is correct |
| 3 |
Correct |
554 ms |
31056 KB |
Output is correct |
| 4 |
Runtime error |
2650 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
