| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 347628 |
2021-01-13T09:35:49 Z |
algorithm16 |
Meteors (POI11_met) |
C++14 |
|
6000 ms |
26196 KB |
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int llint;
llint o[300005],arr[300005],lo[300005],hi[300005],sol[300005];
llint fwt[300005],n,m,k;
vector <pair<pair<int,int>,llint> > v;
vector <llint> ind[300005],v1,l,r;
void update(int x,llint v) {
for(x;x<300005;x+=x&-x) fwt[x]+=v;
}
llint query(int x) {
llint ret=0;
for(x;x>0;x-=x&-x) ret+=fwt[x];
return ret;
}
void f(int l,int r,llint v) {
if(l<=r) {
update(l,v);
update(r+1,-v);
}
else {
update(l,v);
update(m+1,-v);
update(1,v);
update(r+1,-v);
}
//cout << query(1) << " " << query(2) << " " << query(3) << " " << query(4) << " " << query(5) << "\n";
}
llint eval(int x) {
llint ret=0;
for(int i=0;i<ind[x].size();i++) {
ret+=query(ind[x][i]+1);
}
return ret;
}
void clear_fwt() {
for(int i=0;i<300005;i++) fwt[i]=0;
}
void rek(int lo1,int hi1) {
//cout << lo1 << " " << hi1 << "\n";
//system("pause");
if(lo1>hi1) {
for(int i=0;i<v1.size();i++) {
sol[v1[i]]=-1;
}
return;
}
if(lo1==hi1) {
if(hi1==k-1) {
f(v[k-1].first.first,v[k-1].first.second,v[k-1].second);
for(int i=0;i<v1.size();i++) {
if(eval(v1[i])>=arr[v1[i]]) sol[v1[i]]=lo1;
else sol[v1[i]]=-1;
}
return;
}
for(int i=0;i<v1.size();i++) {
sol[v1[i]]=lo1;
}
return;
}
int mid=(lo1+hi1)/2;
for(int i=lo1;i<=mid;i++) {
f(v[i].first.first,v[i].first.second,v[i].second);
}
l.clear();
r.clear();
for(int i=0;i<v1.size();i++) {
if(eval(v1[i])>=arr[v1[i]]) l.push_back(v1[i]);
else r.push_back(v1[i]);
}
//cout << l.size() << " " << r.size() << "\n";
//cout << lo1 << " " << mid << " " << mid+1 << " " << hi1 << "\n";
//system("pause");
v1=r;
rek(mid+1,hi1);
clear_fwt();
v1=l;
rek(lo1,mid);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i=0;i<m;i++) {
cin >> o[i];
ind[o[i]-1].push_back(i);
}
for(int i=0;i<n;i++) {
cin >> arr[i];
v1.push_back(i);
}
cin >> k;
for(int i=0;i<k;i++) {
llint l,r,a;
cin >> l >> r >> a;
v.push_back(make_pair(make_pair(l,r),a));
}
//cout << "abc\n";
//system("pause");
rek(0,k-1);
for(int i=0;i<n;i++) {
if(sol[i]==-1) cout << "NIE\n";
else cout << sol[i]+1 << "\n";
}
return 0;
}
Compilation message
met.cpp: In function 'void update(int, llint)':
met.cpp:11:6: warning: statement has no effect [-Wunused-value]
11 | for(x;x<300005;x+=x&-x) fwt[x]+=v;
| ^
met.cpp: In function 'llint query(int)':
met.cpp:15:6: warning: statement has no effect [-Wunused-value]
15 | for(x;x>0;x-=x&-x) ret+=fwt[x];
| ^
met.cpp: In function 'llint eval(int)':
met.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i=0;i<ind[x].size();i++) {
| ~^~~~~~~~~~~~~~
met.cpp: In function 'void rek(int, int)':
met.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<v1.size();i++) {
| ~^~~~~~~~~~
met.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i=0;i<v1.size();i++) {
| ~^~~~~~~~~~
met.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i=0;i<v1.size();i++) {
| ~^~~~~~~~~~
met.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=0;i<v1.size();i++) {
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
164 ms |
9964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
146 ms |
9836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6097 ms |
11744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6033 ms |
12000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6058 ms |
11872 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6058 ms |
11744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6100 ms |
26196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6078 ms |
25700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
