This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//
// main1.cpp
// problem1
//
// Created by Essa Almousa on 2030 / 01/ 01 AD.
//
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = int;
using ll1 = int;
#define pb push_back
#define pF first
#define pS second
#define SP <<" "<<
const ll N = 3e5+1, offset = 1 << 19;
struct segment {
vector<ll> tree;
void again() {
tree.clear();
tree.resize(2 * offset);
}
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] = min(tree[v] + x, (int)1e9); 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 = min(ans + tree[i], (int)1e9);
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);
ll1 n, m;
cin>>n>>m;
for (ll i=1; i<=m; i++) {
int temp; cin >> temp;
a[i] = temp;
//cin>>a[i];
frq[a[i]].pb(i);
}
for (ll i=1; i<=n; i++) {
int temp; cin >> temp;
b[i] = temp;
//cin>>b[i];
}
ll1 q1;
cin>>q1;
struct binnode { ll i, l, r; };
vector<binnode> bin[N];
for (ll i=1; i<=n; i++) {
ll mi = q1+1/2;
bin[mi].pb({i, 1, q1});
sol[i] = -1;
}
for (ll i=1; i<=q1; i++) {
ll1 l, r, x;
cin>>l>>r>>x;
q[i] = {l, r, x};
}
ll1 cnt = n;
segment tree;
while (cnt > 0) {
tree.again();
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);
while(!bin[i].empty()) {
binnode x = bin[i].back();
bin[i].pop_back();
int ans = 0;
for (auto k : frq[x.i]) {
ans = min(ans + tree.query(k), (int)1e9);
}
if (ans >= b[x.i]) {
sol[x.i] = i;
x.r = i - 1;
}
else {
x.l = i + 1;
}
if (x.l > x.r) {
cnt--;
}
else {
bin[(x.l + x.r) / 2].push_back(x);
}
}
}
}
for (ll i=1; i<=n; i++) {
if (sol[i] == -1) cout << "NIE" << endl;
else cout << sol[i] << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |