| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1012956 |
2024-07-03T02:47:38 Z |
vjudge1 |
Meteors (POI11_met) |
C++14 |
|
592 ms |
65536 KB |
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)>(b)?(b):(a))
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define EDGE(g,i,u,x) for(register int (i)=(g).h[(u)],(x)=(g).v[(i)];(i);(i)=(g).nxt[(i)],(x)=(g).v[(i)])
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=3e5+10;
int n,m,t,tot;
int a[N],p[N],ans[N];
ll sum[N];
struct Modify{
int x,t,v;
friend bool operator <(Modify a,Modify b){
return a.x<b.x;
}
};
#define mid (l+r>>1)
void Bound(int l,int r,vector<Modify> &mo,vector<int> &vec){
for(const int &x:vec)sum[a[x]]=0;
if(l==r){
int it=0;
ll Sum=0;
for(const int &x:vec){
for(;it<mo.size()&&mo[it].x<=x;++it)Sum+=mo[it].v;
if(sum[a[x]]<p[a[x]])sum[a[x]]+=Sum;
}
for(const int &x:vec)ans[a[x]]=(sum[a[x]]>=p[a[x]]?l:-1);
return mo.clear(),vec.clear();
}
vector<Modify> Ls,Rs;
vector<int> ls,rs;
for(const Modify &x:mo)(x.t<=mid?Ls:Rs).push_back(x);
mo.clear();
int it=0;
ll Sum=0;
for(const int &x:vec){
for(;it<Ls.size()&&Ls[it].x<=x;++it)Sum+=Ls[it].v;
if(sum[a[x]]<p[a[x]])sum[a[x]]+=Sum;
}
for(const int &x:vec)(sum[a[x]]>=p[a[x]]?ls:rs).push_back(x);
vec.clear();
for(const int &x:rs)if(~sum[a[x]])p[a[x]]-=sum[a[x]],sum[a[x]]=-1;
Bound(l,mid,Ls,ls),Bound(mid+1,r,Rs,rs);
}
#undef mid
signed main(){
cin>>n>>m;
FOR(i,1,m)cin>>a[i];
FOR(i,1,n)cin>>p[i],ans[i]=-1;
vector<int> vec(m);
vector<Modify> mo;
cin>>t;
FOR(i,1,t){
int l,r,a;cin>>l>>r>>a,++r;
if(l<r){
mo.push_back({l,i,a});
if(r<=m)mo.push_back({r,i,-a});
}else{
mo.push_back({1,i,a});
if(l^r)mo.push_back({r,i,-a}),mo.push_back({l,i,a});
}
}
iota(vec.begin(),vec.end(),1),sort(mo.begin(),mo.end());
Bound(1,t,mo,vec);
FOR(i,1,n){
if(~ans[i])cout<<ans[i]<<endl;
else cout<<"NIE"<<endl;
}
return 0;
}
Compilation message
met.cpp: In function 'void Bound(int, int, std::vector<Modify>&, std::vector<int>&)':
met.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Modify>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(;it<mo.size()&&mo[it].x<=x;++it)Sum+=mo[it].v;
| ~~^~~~~~~~~~
met.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | #define mid (l+r>>1)
| ~^~
met.cpp:39:31: note: in expansion of macro 'mid'
39 | for(const Modify &x:mo)(x.t<=mid?Ls:Rs).push_back(x);
| ^~~
met.cpp:44:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Modify>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(;it<Ls.size()&&Ls[it].x<=x;++it)Sum+=Ls[it].v;
| ~~^~~~~~~~~~
met.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | #define mid (l+r>>1)
| ~^~
met.cpp:50:10: note: in expansion of macro 'mid'
50 | Bound(l,mid,Ls,ls),Bound(mid+1,r,Rs,rs);
| ^~~
met.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | #define mid (l+r>>1)
| ~^~
met.cpp:50:27: note: in expansion of macro 'mid'
50 | Bound(l,mid,Ls,ls),Bound(mid+1,r,Rs,rs);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
10188 KB |
Output is correct |
| 2 |
Correct |
72 ms |
13820 KB |
Output is correct |
| 3 |
Correct |
63 ms |
8764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
9164 KB |
Output is correct |
| 2 |
Correct |
58 ms |
9092 KB |
Output is correct |
| 3 |
Correct |
69 ms |
14016 KB |
Output is correct |
| 4 |
Correct |
31 ms |
5356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
8656 KB |
Output is correct |
| 2 |
Correct |
65 ms |
12484 KB |
Output is correct |
| 3 |
Correct |
36 ms |
7628 KB |
Output is correct |
| 4 |
Correct |
64 ms |
8760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
13652 KB |
Output is correct |
| 2 |
Correct |
60 ms |
11456 KB |
Output is correct |
| 3 |
Correct |
46 ms |
9232 KB |
Output is correct |
| 4 |
Correct |
94 ms |
11908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
406 ms |
58720 KB |
Output is correct |
| 2 |
Correct |
244 ms |
65536 KB |
Output is correct |
| 3 |
Correct |
153 ms |
31988 KB |
Output is correct |
| 4 |
Correct |
535 ms |
49984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
426 ms |
56500 KB |
Output is correct |
| 2 |
Correct |
193 ms |
46244 KB |
Output is correct |
| 3 |
Correct |
134 ms |
23768 KB |
Output is correct |
| 4 |
Correct |
592 ms |
52960 KB |
Output is correct |
