This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
const ll MOD = 1e9 + 7;
void settings()__attribute__((constructor));
// void eval(bool condition) { cout << (condition ? "yes" : "no") << nL; }
// void Eval(bool condition) { cout << (condition ? "Yes" : "No") << nL; }
// void EVAL(bool condition) { cout << (condition ? "YES" : "NO") << nL; }
int ipow(int a, int n) {
if (n == 0) return 1;
int x = ipow(a, n/2);
if (n % 2 == 0) return x*x;
return x*x*a;
}
template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
for (auto elem : v)
stream << elem << " ";
return stream;
}
template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
for(auto &elem : v)
stream >> elem;
return stream;
}
void settings() {
#ifdef LOCAL
freopen("io/input.txt", "r", stdin);
freopen("io/output.txt", "w", stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
}
struct Rain {
int l, r;
int a;
};
int LOG = 19;
struct SegmentTree {
vl t;
SegmentTree(int n) {
t = vl(2*n);
}
void update(int v, int tl, int tr, int l, int r, ll x) {
if (l > r) return;
if (l == tl && r == tr) {
t[v] += x;
return;
}
int tm = (tl+tr)/2;
update(v+1, tl, tm, l, min(r, tm), x);
update(v+2*(tm-tl+1), tm+1, tr, max(tm+1, l), r, x);
}
ll get(int v, int tl, int tr, int pos) {
if (tl > tr) return 0;
if (tl == tr) return t[v];
int tm = (tl+tr)/2;
if (pos <= tm) return t[v]+get(v+1, tl, tm, pos);
else return t[v]+get(v+2*(tm-tl+1), tm+1, tr, pos);
}
};
signed main() {
int n, m;
cin >> n >> m;
vi o(m);
cin >> o;
for (int i = 0; i < m; i++) o[i]--;
vi p(n);
cin >> p;
int k;
cin >> k;
vector<Rain> lr(k);
for (int i = 0; i < k; i++) {
cin >> lr[i].l >> lr[i].r >> lr[i].a;
lr[i].l--; lr[i].r--;
}
vvi c(n);
for (int i = 0; i < m; i++) {
c[o[i]].pb(i);
}
// map<pair<int, pii>, vi> b;
vector<pair<int, pii>> b;
for (int i = 0; i < n; i++) b.pb({i, {0, k-1}});
vi res(n, -1);
SegmentTree tree(m);
while (LOG--) {
tree.t = vl(2*m);
int nxt = 0;
vector<pair<int, pii>> tmp;
for (auto key : b) {
int l = key.second.first, r = key.second.second;
int mid = (l+r)/2;
int u = key.first;
for (int i = nxt; i <= mid; i++) {
if (lr[i].l <= lr[i].r) tree.update(1, 0, m-1, lr[i].l, lr[i].r, lr[i].a);
else {
tree.update(1, 0, m-1, lr[i].l, m-1, lr[i].a);
tree.update(1, 0, m-1, 0, lr[i].r, lr[i].a);
}
nxt++;
}
ll sum = 0;
for (auto v : c[u]) {
sum += tree.get(1, 0, m-1, v);
if (sum >= p[u]) break;
}
// // cout << u << " " << l << " " <<r<< nL;
if (sum < p[u]) {
if (mid+1 <= r) tmp.pb({u, {mid+1, r}});
} else {
if (l <= mid-1)
tmp.pb({u, {l, mid-1}});
if (res[u] == -1) res[u] = mid+1;
else res[u] = min(res[u], mid+1);
}
}
sort(all(tmp), [&](pair<int, pii> a, pair<int, pii> b) {
return (a.second.first+a.second.second)/2 < (b.second.first+b.second.second)/2;
});
b = tmp;
tmp.clear();
}
for (int i = 0; i < n; i++) {
if (res[i] != -1) cout << res[i] << nL;
else cout << "NIE" << nL;
}
return 0;
}
# | 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... |