//
// main1.cpp
// problem1
//
// Created by Essa Almousa on 2030 / 01/ 01 AD.
//
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = unsigned long long;
using ll1 = long long;
#define pb push_back
#define pF first
#define pS second
#define SP <<" "<<
const ll N = 3e5+10;
struct segment {
vector<ll> tree;
ll offset = 1;
void it(ll n) {
while (offset < n) offset *= 2;
tree.resize(offset*2, 0);
}
void upd(ll v, ll l, ll r, ll ql, ll qr, ll x) {
if (l >= qr || r <= ql) return;
if (l >= ql && r <= qr) {tree[v] += x; return;}
ll mi = (l+r)/2;
upd(v*2, l, mi, ql, qr, x);
upd(v*2+1, mi, r, ql, qr, x);
}
ll query(ll i) {
i--;
i += offset;
ll ans = 0;
while (i >= 1) {
ans += tree[i];
i /= 2;
}
return ans;
}
void upd(ll l, ll r, ll val) {return upd(1, 0, offset, l-1, r, val);}
};
struct query_ {
ll l, r, x;
};
ll a[N], b[N];
ll1 sol[N];
vector<ll> frq[N];
query_ q[N];
int main() {
//ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
ll n, m;
cin>>n>>m;
for (ll i=1; i<=m; i++) {
cin>>a[i];
frq[a[i]].pb(i);
}
for (ll i=1; i<=n; i++) cin>>b[i];
ll q1;
cin>>q1;
struct binnode { ll i, m, l, r; };
vector<binnode> bin[N];
for (ll i=1; i<=n; i++) {
ll mi = q1+1/2;
bin[mi].pb({i, mi, 1, q1});
}
for (ll i=1; i<=q1; i++) {
ll l, r, x;
cin>>l>>r>>x;
q[i] = {l, r, x};
sol[i] = -1;
}
ll1 cnt = n;
while (cnt > 0) {
segment tree;
tree.it(m);
for (ll i=1; i<=q1; i++) {
if (q[i].l > q[i].r) {
tree.upd(q[i].l, m, q[i].x);
tree.upd(1, q[i].r, q[i].x);
}
else tree.upd(q[i].l, q[i].r, q[i].x);
for (ll1 j = bin[i].size()-1; j >= 0; j = bin[i].size()-1) {
binnode& x = bin[i][j];
ll ans = 0; // the num
for (ll k=0; k < frq[x.i].size(); k++) ans += tree.query(frq[x.i][k]);
if (ans >= b[x.i]) x.r = x.m;
else {
if (x.l >= q1) {cnt--;bin[i].pop_back(); continue;};
x.l = x.m+1;
}
ll mid = (x.l+x.r)/2;
if (x.l != x.r) {bin[mid].pb({x.i, mid, x.l, x.r}); cnt++;}
else sol[x.i] = x.l;
bin[i].pop_back();
cnt--;
j = bin[i].size() - 1;
}
}
}
for (ll i=1; i<=n; i++) {
if (sol[i] == -1) cout << "NIE" << endl;
else cout << sol[i] << endl;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
15708 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15708 KB |
Output is correct |
| 3 |
Correct |
7 ms |
17888 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
15704 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15896 KB |
Output is correct |
| 3 |
Correct |
7 ms |
15964 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
174 ms |
19152 KB |
Output is correct |
| 2 |
Correct |
218 ms |
20168 KB |
Output is correct |
| 3 |
Correct |
209 ms |
27444 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
208 ms |
25196 KB |
Output is correct |
| 2 |
Correct |
213 ms |
26760 KB |
Output is correct |
| 3 |
Correct |
257 ms |
31836 KB |
Output is correct |
| 4 |
Incorrect |
37 ms |
22224 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
81 ms |
21664 KB |
Output is correct |
| 2 |
Correct |
115 ms |
27300 KB |
Output is correct |
| 3 |
Correct |
100 ms |
17232 KB |
Output is correct |
| 4 |
Correct |
204 ms |
29120 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
214 ms |
18872 KB |
Output is correct |
| 2 |
Correct |
195 ms |
24936 KB |
Output is correct |
| 3 |
Correct |
176 ms |
19908 KB |
Output is correct |
| 4 |
Correct |
249 ms |
33340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
445 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
457 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
