| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 32128 |
2017-09-27T18:24:58 Z |
dereotu |
Meteors (POI11_met) |
C++14 |
|
3309 ms |
61548 KB |
#include <bits/stdc++.h>
#define endl '\n'
#define space ' '
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define ii pair <int,int>
#define iii pair <int,pair<int,int> >
#define vi vector <int>
#define vii vector < pair<int,int> >
#define forr(i,A,B) for(int i=A;i<B;++i)
#define input(file) freopen(file,"r",stdin)
#define output(file) freopen(file,"w",stdout)
#define time hdsadas
#define edge xasdafsaf
#define y1 dsafgsdfs
#define MAXX 10
#define mod 1000000007
using namespace std;
typedef pair<pair<int,int>,pair<int,int> > edge;
inline void read(int &x){
scanf(" %d",&x);
}
const int maxn=3*100005;
vector <int> owner[maxn],tocheck[maxn];
int n,m,k,ql[maxn],qr[maxn],lo[maxn],hi[maxn],x;
long long sum,fw[maxn],need[maxn],qa[maxn];
void upd(int x,long long val){
if(x==0) return;
for(;x<=m;x+=(x&-x)){
fw[x]+=val;
}
}
long long que(int x){
long long ret=0;
for(;x>0;x-=(x&-x))
ret+=fw[x];
return ret;
}
void shower(int x){
if(ql[x]<=qr[x]){
upd(ql[x],qa[x]);
upd(qr[x]+1,-qa[x]);
}
else{
upd(1,qa[x]);
upd(qr[x]+1,-qa[x]);
upd(ql[x],qa[x]);
}
}
#undef int
int main(){
#define int long long
//ios_base::sync_with_stdio(false);
//cin.tie(0);
cin>>n>>m;
forr(i,0,m){
int x;
cin>>x;
owner[x].pb(i+1);
}
forr(i,0,n){
cin>>need[i+1];
}
cin>>k;
forr(i,1,k+1){
cin>>ql[i]>>qr[i]>>qa[i];
}
forr(i,1,n+1){
lo[i]=1;
hi[i]=k+1;
}
bool notdone=true;
while(notdone){
notdone=false;
memset(fw,0,sizeof fw);
forr(i,1,n+1){
if(lo[i]!=hi[i]) tocheck[(lo[i]+hi[i])/2].pb(i);
}
forr(i,1,k+1){
shower(i);
while(!tocheck[i].empty()){
notdone=true;
sum=0;
int id=tocheck[i].back();
tocheck[i].pop_back();
forr(j,0,owner[id].size()){
sum+=que(owner[id][j]);
assert(sum>=0);
if(sum>=need[id]) break;
}
if(sum>=need[id]){
hi[id]=i;
}
else{
lo[id]=i+1;
}
}
}
}
forr(i,1,n+1){
if(lo[i]==k+1) cout<<"NIE\n";
else cout<<lo[i]<<endl;
}
return 0;
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:12:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define forr(i,A,B) for(int i=A;i<B;++i)
^
met.cpp:93:5: note: in expansion of macro 'forr'
forr(j,0,owner[id].size()){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
27796 KB |
Output is correct |
| 2 |
Correct |
3 ms |
27796 KB |
Output is correct |
| 3 |
Correct |
6 ms |
27796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
27796 KB |
Output is correct |
| 2 |
Correct |
6 ms |
27796 KB |
Output is correct |
| 3 |
Correct |
16 ms |
27928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
28664 KB |
Output is correct |
| 2 |
Correct |
226 ms |
30532 KB |
Output is correct |
| 3 |
Correct |
189 ms |
30060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
29520 KB |
Output is correct |
| 2 |
Correct |
203 ms |
29528 KB |
Output is correct |
| 3 |
Correct |
266 ms |
30772 KB |
Output is correct |
| 4 |
Correct |
49 ms |
29384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
28992 KB |
Output is correct |
| 2 |
Correct |
176 ms |
31024 KB |
Output is correct |
| 3 |
Correct |
96 ms |
27928 KB |
Output is correct |
| 4 |
Correct |
183 ms |
30384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
28220 KB |
Output is correct |
| 2 |
Correct |
196 ms |
29532 KB |
Output is correct |
| 3 |
Correct |
143 ms |
28456 KB |
Output is correct |
| 4 |
Correct |
223 ms |
31620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1976 ms |
41296 KB |
Output is correct |
| 2 |
Correct |
1359 ms |
30448 KB |
Output is correct |
| 3 |
Correct |
439 ms |
27928 KB |
Output is correct |
| 4 |
Correct |
3206 ms |
57956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2083 ms |
40500 KB |
Output is correct |
| 2 |
Correct |
1303 ms |
29932 KB |
Output is correct |
| 3 |
Correct |
456 ms |
27928 KB |
Output is correct |
| 4 |
Correct |
3309 ms |
61548 KB |
Output is correct |
