oj.uz

답안 #418243

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418243 2021-06-05T08:40:03 Z jamezzz Meteors (POI11_met) C++17
74 / 100
 1038 ms 35828 KB 
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;

struct query{ int s,e;vi v; };
queue<query> q;

int n,m,o,p[300005],k,l[300005],r[300005],a[300005],ans[300005];
ll ft[300005];
vi s[300005];

void up(int x,int v){
	while(x<=m)ft[x]+=v,x+=x&-x;
}
ll qry(int x){
	ll res=0;
	while(x)res+=ft[x],x-=x&-x;
	return res;
}

int main(){
	sf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		sf("%d",&o);
		s[o].pb(i);
	}
	for(int i=1;i<=n;++i)sf("%d",&p[i]);
	sf("%d",&k);
	for(int i=1;i<=k;++i){
		sf("%d%d%d",&l[i],&r[i],&a[i]);
	}
	l[k+1]=1;r[k+1]=m;a[k+1]=1e9;
	query x={1,k+1};
	for(int i=1;i<=n;++i)x.v.pb(i);
	q.push(x);
	int pv=0;
	while(!q.empty()){
		query x={0,0};
		swap(x,q.front());
		q.pop();
		if(x.s==x.e){
			for(int i:x.v)ans[i]=x.s;
			continue;
		}
		int md=(x.s+x.e)/2;
		query nl={x.s,md},nr={md+1,x.e};
		if(md<pv)memset(ft,0,sizeof ft),pv=0;
		while(pv!=md){
			++pv;
			if(l[pv]<=r[pv]){
				up(l[pv],a[pv]);
				up(r[pv]+1,-a[pv]);
			}
			else{
				up(1,a[pv]);
				up(r[pv]+1,-a[pv]);
				up(l[pv],a[pv]);
			}
		}
		for(int i:x.v){
			ll tot=0;
			for(int j:s[i])tot+=qry(j);
			if(tot>=p[i])nl.v.pb(i);
			else nr.v.pb(i);
		}
		q.push(nl);q.push(nr);
	}
	for(int i=1;i<=n;++i){
		if(ans[i]<=k)pf("%d\n",ans[i]);
		else pf("NIE\n");
	}
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:31:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  sf("%d%d",&n,&m);
      |    ^
met.cpp:33:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   sf("%d",&o);
      |     ^
met.cpp:36:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  for(int i=1;i<=n;++i)sf("%d",&p[i]);
      |                         ^
met.cpp:37:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  sf("%d",&k);
      |    ^
met.cpp:39:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   sf("%d%d%d",&l[i],&r[i],&a[i]);
      |     ^

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9804 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9792 KB Output is correct
2 Correct 7 ms 9700 KB Output is correct
3 Correct 8 ms 9804 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 12616 KB Output is correct
2 Correct 119 ms 13992 KB Output is correct
3 Correct 99 ms 13620 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 13284 KB Output is correct
2 Correct 102 ms 13256 KB Output is correct
3 Correct 119 ms 13824 KB Output is correct
4 Correct 36 ms 11304 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 12740 KB Output is correct
2 Correct 99 ms 14200 KB Output is correct
3 Correct 50 ms 12124 KB Output is correct
4 Correct 101 ms 13760 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 12752 KB Output is correct
2 Correct 122 ms 13460 KB Output is correct
3 Correct 90 ms 12752 KB Output is correct
4 Correct 120 ms 14316 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1006 ms 35828 KB Output is correct
2 Incorrect 686 ms 30908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1038 ms 35196 KB Output is correct
2 Incorrect 692 ms 29500 KB Output isn't correct
3 Halted 0 ms 0 KB -