| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 389725 |
2021-04-14T12:10:39 Z |
qwerasdfzxcl |
Meteors (POI11_met) |
C++14 |
|
3406 ms |
65540 KB |
#include <bits/stdc++.h>
#define ll __int128_t
#define int long long
using namespace std;
struct Seg{
ll tree[600600];
int sz;
void init(){
for (int i=1;i<((sz)<<1);i++) tree[i] = 0;
}
void update_p(int i, int p){
i += sz;
for (tree[i]+=p;i>1;i>>=1) tree[i>>1] = tree[i]+tree[i^1];
}
void update(int l, int r, int p){
update_p(l, p);
if (r<sz-1) update_p(r+1, -p);
}
ll query(int l, int r){
ll ret = 0;
for (l += sz, r += sz;l<r;l>>=1, r>>=1){
if (l&1) ret += tree[l++];
if (r&1) ret += tree[--r];
}
return ret;
}
void debug(){
for (int i=sz;i<(sz<<1);i++) printf("%lld ", tree[i]);
printf("\n");
}
}tree;
struct Query{
int l, r, a;
}query[300300];
vector<int> ar[300300], q[300300];
int l[300300], r[300300], ans[300300];
int val[300300];
signed main(){
int n, m;
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> m;
tree.sz = m+1;
for (int i=1;i<=m;i++){
int x;
cin >> x;
ar[x-1].push_back(i);
}
for (int i=0;i<n;i++) cin >> val[i];
int tmp;
cin >> tmp;
for (int i=0;i<tmp;i++){
cin >> query[i].l >> query[i].r >> query[i].a;
}
for (int i=0;i<n;i++) l[i] = 0, r[i] = tmp;
while(1){
//assert(c<12);
bool chk=0;
for (int i=0;i<=tmp;i++) q[i].clear();
for (int i=0;i<n;i++) if (l[i]!=r[i]){
q[(l[i]+r[i])>>1].push_back(i);
chk=1;
}
if (!chk) break;
tree.init();
for (int i=0;i<tmp;i++){
if (query[i].l<=query[i].r) tree.update(query[i].l, query[i].r, query[i].a);
else{
tree.update(1, query[i].r, query[i].a);
tree.update(query[i].l, m, query[i].a);
}
for (auto &j:q[i]){
ll tmp1 = 0;
for (auto &x:ar[j]){
tmp1 += tree.query(1, x+1);
}
if (tmp1>=val[j]){
r[j] = i;
ans[j] = i+1;
}
else l[j] = i+1;
}
//tree.debug();
}
}
for (int i=0;i<n;i++){
if (l[i] == tmp) cout << "NIE\n";
else cout << ans[i] << '\n';
}
return 0;
}
Compilation message
met.cpp: In member function 'void Seg::debug()':
met.cpp:29:49: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type '__int128' [-Wformat=]
29 | for (int i=sz;i<(sz<<1);i++) printf("%lld ", tree[i]);
| ~~~^ ~~~~~~~
| | |
| | __int128
| long long int
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14540 KB |
Output is correct |
| 2 |
Correct |
10 ms |
14540 KB |
Output is correct |
| 3 |
Correct |
12 ms |
14528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14540 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14504 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
18616 KB |
Output is correct |
| 2 |
Correct |
225 ms |
21876 KB |
Output is correct |
| 3 |
Correct |
224 ms |
20896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
225 ms |
20068 KB |
Output is correct |
| 2 |
Correct |
201 ms |
20140 KB |
Output is correct |
| 3 |
Correct |
250 ms |
22460 KB |
Output is correct |
| 4 |
Correct |
73 ms |
19200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
19080 KB |
Output is correct |
| 2 |
Correct |
166 ms |
22512 KB |
Output is correct |
| 3 |
Correct |
60 ms |
15696 KB |
Output is correct |
| 4 |
Correct |
202 ms |
21676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
17768 KB |
Output is correct |
| 2 |
Correct |
192 ms |
20044 KB |
Output is correct |
| 3 |
Correct |
157 ms |
18256 KB |
Output is correct |
| 4 |
Correct |
266 ms |
23688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3330 ms |
55576 KB |
Output is correct |
| 2 |
Correct |
995 ms |
33376 KB |
Output is correct |
| 3 |
Correct |
286 ms |
22852 KB |
Output is correct |
| 4 |
Runtime error |
2610 ms |
65540 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3406 ms |
53444 KB |
Output is correct |
| 2 |
Correct |
834 ms |
33420 KB |
Output is correct |
| 3 |
Correct |
234 ms |
22760 KB |
Output is correct |
| 4 |
Runtime error |
1635 ms |
65540 KB |
Execution killed with signal 9 |
