| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 964742 |
2024-04-17T13:08:17 Z |
BhavayGoyal |
Meteors (POI11_met) |
C++14 |
|
1554 ms |
51116 KB |
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"
const int MOD = 1e9+7;
const int inf = 1e9;
const int linf = 1e18;
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// -------------------------------------------------- Main Code --------------------------------------------------
struct bit {
int n;
vi tree;
bit(int N) {n = N+5; tree = vi(n+2);}
void update(int idx, int val) { for (idx; idx <= n; idx += (idx&-idx)) tree[idx] += val; }
int sum(int idx) { int ans = 0; for (idx; idx; idx -= (idx&-idx)) ans += tree[idx]; return ans; }
};
struct state { int l, r; };
void sol() {
int n, m; cin >> n >> m;
int req[n+1], ans[n+1];
vi positions[n+1];
for (int i = 1; i <= n; i++) ans[i] = -1;
for (int i = 1; i <= m; i++) {
int x; cin >> x;
positions[x].pb(i);
}
for (int i = 1; i <= n; i++) cin >> req[i];
int q; cin >> q;
array<int, 3> queries[q+1];
for (int i = 1; i <= q; i++) {
int a, b, c; cin >> a >> b >> c;
queries[i] = {a, b, c};
}
state currState[n+1];
for (int i = 1; i <= n; i++) currState[i] = {1, q};
int counter = n;
while (counter) {
vector<int> query[q+1];
int newCounter = 0;
for (int i = 1; i <= n; i++) {
if (currState[i].l > currState[i].r) continue;
int mid = (currState[i].l+currState[i].r)/2;
query[mid].push_back(i);
newCounter++;
}
counter = newCounter;
bit tree(m+5);
for (int i = 1; i <= q; i++) {
int l = queries[i][0], r = queries[i][1], val = queries[i][2];
if (l > r) {
swap(l, r);
tree.update(r, val);
tree.update(1, val);
tree.update(l+1, -val);
}
else {
tree.update(l, val);
tree.update(r+1, -val);
}
for (auto j : query[i]) {
int ct = 0;
for (auto x : positions[j]) {
ct += tree.sum(x);
if (ct > inf) break;
}
int &l = currState[j].l, &r = currState[j].r;
if (ct >= req[j]) r = i-1, ans[j] = i;
else l = i+1;
}
}
}
for (int i = 1; i <= n; i++) {
if (ans[i] == -1) cout << "NIE" << endl;
else cout << ans[i] << endl;
}
}
signed main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) {
sol();
}
return 0;
}
Compilation message
met.cpp: In member function 'void bit::update(long long int, long long int)':
met.cpp:40:42: warning: statement has no effect [-Wunused-value]
40 | void update(int idx, int val) { for (idx; idx <= n; idx += (idx&-idx)) tree[idx] += val; }
| ^~~
met.cpp: In member function 'long long int bit::sum(long long int)':
met.cpp:41:42: warning: statement has no effect [-Wunused-value]
41 | int sum(int idx) { int ans = 0; for (idx; idx; idx -= (idx&-idx)) ans += tree[idx]; return ans; }
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
4152 KB |
Output is correct |
| 2 |
Correct |
89 ms |
5868 KB |
Output is correct |
| 3 |
Correct |
69 ms |
4936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
4584 KB |
Output is correct |
| 2 |
Correct |
71 ms |
4596 KB |
Output is correct |
| 3 |
Correct |
84 ms |
5852 KB |
Output is correct |
| 4 |
Correct |
21 ms |
2908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
4236 KB |
Output is correct |
| 2 |
Correct |
73 ms |
6084 KB |
Output is correct |
| 3 |
Correct |
34 ms |
2860 KB |
Output is correct |
| 4 |
Correct |
71 ms |
5268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
3692 KB |
Output is correct |
| 2 |
Correct |
72 ms |
4564 KB |
Output is correct |
| 3 |
Correct |
51 ms |
3932 KB |
Output is correct |
| 4 |
Correct |
96 ms |
5944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
840 ms |
30336 KB |
Output is correct |
| 2 |
Correct |
629 ms |
19276 KB |
Output is correct |
| 3 |
Correct |
183 ms |
14584 KB |
Output is correct |
| 4 |
Correct |
1308 ms |
47356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
799 ms |
29136 KB |
Output is correct |
| 2 |
Correct |
721 ms |
19248 KB |
Output is correct |
| 3 |
Correct |
159 ms |
13284 KB |
Output is correct |
| 4 |
Correct |
1554 ms |
51116 KB |
Output is correct |
