Submission #587713

#TimeUsernameProblemLanguageResultExecution timeMemory
587713LittlePantsMeteors (POI11_met)C++17
100 / 100
684 ms65536 KiB
#define ll loli #include<bits/stdc++.h> #define pb push_back #define eb emplace_back #define push emplace #define lb(x, v) lower_bound(all(x), v) #define ub(x, v) upper_bound(all(x), v) #define sz(x) (int)(x.size()) #define re(x) reverse(all(x)) #define uni(x) x.resize(unique(all(x)) - x.begin()) #define all(x) x.begin(), x.end() #define mem(x, v) memset(x, v, sizeof x); #define int long long #define pii pair<int, int> #define inf 1000000000 #define INF 1000000000000000000 #define mod 1000000007 #define F first #define S second #define IO ios_base::sync_with_stdio(0); cin.tie(0); #define chmax(a, b) (a = (b > a ? b : a)) #define chmin(a, b) (a = (b < a ? b : a)) #define get_bit(x, y) ((x>>y)&1) #define mkp make_pair using namespace std; #ifdef loli void trace_() {cerr << "\n";} template<typename T1, typename... T2> void trace_(T1 t1, T2... t2) {cerr << ' ' << t1; trace_(t2...); } #define trace(...) cerr << "[" << #__VA_ARGS__ << "] :", trace_(__VA_ARGS__); #else #define trace(...) 49 #endif const int mxN = 3e5 + 5, mxA = 10000000000; int n, m, k, ans[mxN]; unsigned int sum[mxN], a[mxN]; int tot; array<int, 3> v[mxN * 5], tmp[mxN * 5]; bool cmp(array<int, 3> a, array<int, 3> b) { if (a[1] == b[1]) return (a[0] == 0 ? INF : a[0]) < (b[0] == 0 ? INF : b[0]); return a[1] < b[1]; } void bs(int l, int r, int ql, int qr) { if (l == r) { for (int j = ql; j <= qr; j++) { auto [i, p, o] = v[j]; if (!i) ans[o] = l; } return; } int mid = (l + r) / 2; unsigned res = 0; for (int j = ql; j <= qr; j++) { auto [i, x, val] = v[j]; if (i and i <= mid) res += val; if (!i) sum[val] += res; } int tl = ql, tr = qr; for (int j = ql; j <= qr; j++) { auto [i, x, val] = v[j]; if (i) { if (i <= mid) tmp[tl++] = v[j]; else tmp[tr--] = v[j]; } else { if (a[val] <= sum[val]) tmp[tl++] = v[j]; else tmp[tr--] = v[j]; } } reverse(tmp + tl, tmp + qr + 1); copy(tmp + ql, tmp + qr + 1, v + ql); res = 0; for (int j = ql; j < tl; j++) { auto [i, x, val] = v[j]; if (i) res += val; else sum[val] -= res; } bs(l, mid, ql, tr); bs(mid+1, r, tl, qr); } inline void solve() { cin >> n >> m; vector<int> o(m + 1); for (int i = 1; i <= m; i++) cin >> o[i]; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++) v[tot++] = {0, i, o[i]}; cin >> k; for (int i = 1; i <= k; i++) { int l, r, x; cin >> l >> r >> x; if (l > r) { v[tot++] = {i, l, x}; v[tot++] = {i, 1, x}; v[tot++] = {i, r + 1, -x}; } else { v[tot++] = {i, l, x}; if (r + 1 <= m) v[tot++] = {i, r + 1, -x}; } } sort(v, v + tot, cmp); bs(1, k + 1, 0, tot - 1); for (int i = 1; i <= n; i++) { if (ans[i] == 0 or ans[i] == k + 1) cout << "NIE\n"; else cout << ans[i] << '\n'; } } signed main() { IO; solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...