제출 #1049681

#제출 시각아이디문제언어결과실행 시간메모리
1049681QuangBui새로운 문제 (POI11_met)C++17
74 / 100
277 ms37468 KiB
// QuangBuiCP // https://oj.uz/problem/view/POI11_met #include "bits/stdc++.h" using namespace std; #define int long long const int N = (int) 3e5 + 5; int n, m, events; int64_t Bit[N]; void Update(int x, int64_t val) { while (x <= m) { Bit[x] += val; x += x & -x; } } void Update(int from, int to, int64_t val) { Update(from, val); Update(to + 1, -val); if (from > to) { Update(1, val); Update(m + 1, -val); } } int64_t Query(int x) { int64_t res = 0; while (x >= 1) { res += Bit[x]; x -= x & -x; } return res; } vector<int> properties[N]; int64_t target[N]; int L[N], R[N]; int64_t collectable[N]; int answer[N]; // [from, to) void BinarySearch(int from, int to, vector<int>& candidates) { if (from + 1 == to || candidates.empty()) { for (int cand : candidates) { answer[cand] = from; } return; } int mid = (from + to) / 2; for (int i = from; i < mid; ++i) { Update(L[i], R[i], collectable[i]); } vector<int> doable, not_doable; for (int who : candidates) { int64_t sum = 0; for (int land : properties[who]) { sum += Query(land); } if (sum >= target[who]) { doable.push_back(who); } else { target[who] -= sum; not_doable.push_back(who); } } for (int i = from; i < mid; ++i) { Update(L[i], R[i], -collectable[i]); } BinarySearch(from, mid, doable); BinarySearch(mid, to, not_doable); doable.clear(); not_doable.clear(); } signed main() { #ifndef LOCAL cin.tie(nullptr)->sync_with_stdio(false); #endif // LOCAL cin >> n >> m; for (int i = 1; i <= m; ++i) { int who; cin >> who; properties[who].push_back(i); } for (int i = 1; i <= n; ++i) { cin >> target[i]; } cin >> events; for (int i = 0; i < events; ++i) { cin >> L[i] >> R[i] >> collectable[i]; } vector<int> owners(n); iota(owners.begin(), owners.end(), 1); BinarySearch(0, events + 1, owners); for (int i = 1; i <= n; ++i) { if (answer[i] == events) { cout << "NIE\n"; } else { cout << answer[i] + 1 << '\n'; } } 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...