oj.uz

답안 #32124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
32124 2017-09-27T17:20:14 Z dereotu Meteors (POI11_met) C++14
61 / 100
 1736 ms 37780 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,fw[maxn],need[maxn],sum;
vector <int> owner[maxn],tocheck[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>>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]);
				}
				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:90:5: note: in expansion of macro 'forr'
     forr(j,0,owner[id].size()){
     ^

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 24280 KB Output is correct
2 Correct 6 ms 24280 KB Output is correct
3 Correct 9 ms 24280 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 24280 KB Output is correct
2 Correct 6 ms 24280 KB Output is correct
3 Correct 0 ms 24412 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 25148 KB Output is correct
2 Correct 219 ms 27016 KB Output is correct
3 Correct 199 ms 26544 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 26004 KB Output is correct
2 Correct 199 ms 26012 KB Output is correct
3 Correct 246 ms 27256 KB Output is correct
4 Correct 49 ms 25868 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 25476 KB Output is correct
2 Correct 256 ms 27508 KB Output is correct
3 Correct 149 ms 24412 KB Output is correct
4 Correct 183 ms 26868 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 189 ms 24704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1736 ms 37780 KB Output is correct
2 Incorrect 1163 ms 26932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1706 ms 36984 KB Output is correct
2 Incorrect 1113 ms 26416 KB Output isn't correct
3 Halted 0 ms 0 KB -