| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 555090 |
2022-04-30T07:12:08 Z |
myungwoo |
Meteors (POI11_met) |
C++17 |
|
1921 ms |
65536 KB |
#include <cstdio>
#include <vector>
using namespace std;
typedef unsigned long long ull;
vector<int> sect[300001];
vector<vector<int> > cp;
ull goal[300001];
struct Day{
int l,r; ull cnt;
Day(){} Day(int l, int r, ull cnt):l(l),r(r),cnt(cnt){}
};
struct Fenwick{
int s,e;
vector<ull> tree, tadd;
Fenwick(){} Fenwick(int n):s(1),e(n),tree(n+1,0ULL){}
void clear() { tree.clear(); tree.resize(e+1,0ULL); }
void rupdate(int left, int right, ull by) {
inupdate(left, by);
inupdate(right+1, -by);
}
void inupdate(int at, ull by) {
for(int i=at; i<=e && i; i+=i&-i) tree[i]+=by;
}
ull query(int at) {
ull ans=0ULL;
for(int i=at; i>=1; i&=(i-1)) ans+=tree[i];
return ans;
}
};
vector<Day> day(1);
int l[300001], r[300001];
int main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) {
int x; scanf("%d",&x);
sect[x].push_back(i);
}
Fenwick fen(m);
for(int i=1; i<=n; i++) {
scanf("%llu",&goal[i]);
}
int q; scanf("%d",&q);
for(int i=1; i<=q; i++) {
int l,r; ull cnt;
scanf("%d%d%llu",&l,&r,&cnt);
day.push_back(Day(l,r,cnt));
}
cp.resize(q+1, vector<int>());
for(int i=1; i<=n; i++) l[i]=0, r[i]=q+1;
while(true) {
bool good=false;
for(int i=1; i<=n; i++) {
if(l[i]+1<r[i]) {
cp[(l[i]+r[i])>>1].push_back(i);
good=true;
}
}
if(!good) break;
int pi=1;
for(int i=1; i<=q; i++) {
//bring meteor shower!!
if(!cp[i].size()) continue;
for(int j=pi; j<=i; pi=++j) {
if(day[j].l<=day[j].r) {
fen.rupdate(day[j].l,day[j].r,day[j].cnt);
} else {
fen.rupdate(1,day[j].r,day[j].cnt);
fen.rupdate(day[j].l,m,day[j].cnt);
}
}
for(int nara: cp[i]) {
ull sum=0ULL;
for(int k: sect[nara]) sum+=fen.query(k);
int mid=(l[nara]+r[nara])>>1;
if(sum>=goal[nara]) r[nara]=mid;
else l[nara]=mid;
}
cp[i].clear();
}
fen.clear();
}
for(int i=1; i<=n; i++) {
if(r[i]!=q+1) printf("%d\n", r[i]);
else puts("NIE");
}
return 0;
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
met.cpp:37:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | int x; scanf("%d",&x);
| ~~~~~^~~~~~~~~
met.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%llu",&goal[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:44:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | int q; scanf("%d",&q);
| ~~~~~^~~~~~~~~
met.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d%d%llu",&l,&r,&cnt);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
6 ms |
7380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
10512 KB |
Output is correct |
| 2 |
Correct |
115 ms |
12488 KB |
Output is correct |
| 3 |
Correct |
112 ms |
12172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
11684 KB |
Output is correct |
| 2 |
Correct |
104 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
129 ms |
12672 KB |
Output is correct |
| 4 |
Correct |
34 ms |
9724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
10972 KB |
Output is correct |
| 2 |
Correct |
94 ms |
13172 KB |
Output is correct |
| 3 |
Correct |
34 ms |
9468 KB |
Output is correct |
| 4 |
Correct |
102 ms |
12560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
10000 KB |
Output is correct |
| 2 |
Correct |
99 ms |
11560 KB |
Output is correct |
| 3 |
Correct |
81 ms |
10304 KB |
Output is correct |
| 4 |
Correct |
122 ms |
13856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1012 ms |
35360 KB |
Output is correct |
| 2 |
Correct |
261 ms |
22808 KB |
Output is correct |
| 3 |
Correct |
178 ms |
19644 KB |
Output is correct |
| 4 |
Correct |
1734 ms |
63192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
996 ms |
34208 KB |
Output is correct |
| 2 |
Correct |
547 ms |
22752 KB |
Output is correct |
| 3 |
Correct |
101 ms |
18696 KB |
Output is correct |
| 4 |
Correct |
1921 ms |
65536 KB |
Output is correct |
