oj.uz

답안 #748273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
748273 2023-05-26T03:08:18 Z jamezzz Meteors (POI11_met) C++17
74 / 100
 874 ms 30888 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define sf scanf
#define pf printf
#define fi first
#define se second
#define INF 1023456789
#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;
		ft[x]=min(ft[x],(ll)INF);
		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:36:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  sf("%d%d",&n,&m);
      |    ^
met.cpp:38:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   sf("%d",&o);
      |     ^
met.cpp:41:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  for(int i=1;i<=n;++i)sf("%d",&p[i]);
      |                         ^
met.cpp:42:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  sf("%d",&k);
      |    ^
met.cpp:44:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   sf("%d%d%d",&l[i],&r[i],&a[i]);
      |     ^

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 8 ms 9812 KB Output is correct
3 Correct 7 ms 9784 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 11856 KB Output is correct
2 Correct 110 ms 13928 KB Output is correct
3 Correct 90 ms 13564 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 12208 KB Output is correct
2 Correct 101 ms 13388 KB Output is correct
3 Correct 104 ms 13808 KB Output is correct
4 Correct 30 ms 11352 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 11980 KB Output is correct
2 Correct 87 ms 14372 KB Output is correct
3 Correct 46 ms 11972 KB Output is correct
4 Correct 89 ms 13896 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 11688 KB Output is correct
2 Correct 92 ms 13388 KB Output is correct
3 Correct 73 ms 12836 KB Output is correct
4 Correct 105 ms 14376 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 824 ms 27892 KB Output is correct
2 Incorrect 523 ms 30888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 874 ms 27476 KB Output is correct
2 Incorrect 520 ms 29380 KB Output isn't correct
3 Halted 0 ms 0 KB -