제출 #418243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418243		jamezzz	새로운 문제 (POI11_met)	C++17	74 / 100	1038 ms	35828 KiB

met

#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");
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13