Submission #748272

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
748272	2023-05-26T03:08:00 Z	jamezzz	Meteors (POI11_met)	C++17	0 / 100	832 ms	35912 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]=max(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
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	9728 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	7 ms	9684 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	62 ms	12612 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	92 ms	13060 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	70 ms	12620 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	88 ms	12632 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	832 ms	35912 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	807 ms	35348 KB	Output isn't correct
2	Halted	0 ms	0 KB	-