Submission #1089264

#TimeUsernameProblemLanguageResultExecution timeMemory
1089264TrinhKhanhDungMeteors (POI11_met)C++14
74 / 100
1065 ms29856 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define sz(x) (int)x.size() #define ALL(v) v.begin(),v.end() #define MASK(k) (1LL << (k)) #define BIT(x, i) (((x) >> (i)) & 1) #define oo (ll)1e18 #define INF (ll)1e9 #define MOD (ll)(1e9 + 7) using namespace std; template<class T1, class T2> bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;} template<class T1, class T2> bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;} template<class T1, class T2> void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;} template<class T1, class T2> void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;} template<class T> void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());} struct fen{ vector<ll> tree; int n; fen(int _n = 0){ n = _n; tree.resize(n + 3, 0); } void upd(int p, ll c){ while(p <= n){ tree[p] += c; p += p & -p; } } ll get(int p){ ll ans = 0; while(p){ ans += tree[p]; p -= p & -p; } return ans; } }; const int MAX = 3e5 + 10; int N, M, Q; int a[MAX], L[MAX], R[MAX], ans[MAX]; vector<int> pos[MAX]; vector<array<int, 3>> upds; int cnp(){ int cnt = 0; vector<pair<int, int>> ord; for(int i = 1; i <= N; i++) if(L[i] <= R[i]){ cnt++; int m = (L[i] + R[i]) >> 1; ord.push_back(make_pair(m, i)); } sort(ALL(ord)); int j = 0; fen bit(M); for(int i = 0; i < Q; i++){ int l = upds[i][0], r = upds[i][1], c = upds[i][2]; bit.upd(l, c); bit.upd(r + 1, -c); if(l > r){ bit.upd(1, c); } while(j < sz(ord) && ord[j].fi == i){ int id = ord[j].se, m = ord[j].fi; j++; ll sum = 0; for(int x: pos[id]) sum += bit.get(x); if(sum >= a[id]){ R[id] = m - 1; ans[id] = m; } else L[id] = m + 1; } } return cnt; } void solve(){ cin >> N >> M; for(int i = 1; i <= M; i++){ int x; cin >> x; pos[x].push_back(i); } for(int i = 1; i <= N; i++) cin >> a[i]; cin >> Q; for(int i = 1; i <= Q; i++){ int x, y, z; cin >> x >> y >> z; upds.push_back({x, y, z}); } for(int i = 1; i <= N; i++){ L[i] = 0; R[i] = Q - 1; } memset(ans, -1, sizeof ans); // cnp(); while(cnp()); for(int i = 1; i <= N; i++){ if(ans[i] == -1) cout << "NIE\n"; else cout << ans[i] + 1 << '\n'; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("order.inp","r",stdin); // freopen("order.out","w",stdout); int t = 1; // cin >> t; while(t--){ solve(); } return 0; }
#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...