# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
32126 |
2017-09-27T17:34:51 Z |
dereotu |
Meteors (POI11_met) |
C++14 |
|
1586 ms |
38928 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;
int n,m,k,qa[maxn],ql[maxn],qr[maxn],lo[maxn],hi[maxn],x,need[maxn];
vector <int> owner[maxn],tocheck[maxn];
long long sum,fw[maxn];
void upd(int x,int val){
if(x==0) return;
for(;x<maxn;x+=(x&-x)){
fw[x]+=val;
}
}
int que(int x){
int 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]);
}
}
int main(){
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()){
if(sum>=need[id]) break;
sum+=que(owner[id][j]);
}
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:92:5: note: in expansion of macro 'forr'
forr(j,0,owner[id].size()){
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
25612 KB |
Output is correct |
2 |
Correct |
9 ms |
25612 KB |
Output is correct |
3 |
Correct |
13 ms |
25612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
25612 KB |
Output is correct |
2 |
Correct |
16 ms |
25612 KB |
Output is correct |
3 |
Correct |
3 ms |
25612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
109 ms |
26340 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
183 ms |
27384 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
163 ms |
26808 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
25936 KB |
Output is correct |
2 |
Runtime error |
203 ms |
27276 KB |
Execution killed because of forbidden syscall writev (20) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1553 ms |
38928 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1586 ms |
38276 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Halted |
0 ms |
0 KB |
- |