Submission #748286

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
748286	2023-05-26T03:25:25 Z	jamezzz	Meteors (POI11_met)	C++17	74 / 100	6000 ms	65536 KB

#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define pb push_back
#define INF 1023456789
typedef long long ll;
typedef vector<int> vi;

struct node{
	int s,e,m;ll v,lz;
	node *l,*r;
	node(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1,v=0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void reset(){
		v=0;
		if(s!=e)l->reset(),r->reset();
	}
	void up(int x,int y,int nv){
		if(s==x&&e==y){v+=nv;return;}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
	}
	ll qry(int x){
		if(s==x&&e==x)return v;
		if(x<=m)return v+l->qry(x);
		else return v+r->qry(x);
	}
}*rt;

#define maxn 300005

int n,m,p[maxn],k,l[maxn],r[maxn],a[maxn],ans[maxn];
vi s[maxn];

int main(){
	sf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int o;sf("%d",&o);
		s[o].pb(i);
	}
	vi v;
	for(int i=1;i<=n;++i){
		sf("%d",&p[i]);
		v.pb(i);
		ans[i]=-1;
	}
	sf("%d",&k);
	for(int i=1;i<=k;++i)sf("%d%d%d",&l[i],&r[i],&a[i]);
	queue<tuple<int,int,vi>> q;
	q.push({1,k,v});
	int pv=0;
	rt=new node(1,m);
	while(!q.empty()){
		auto[lo,hi,v]=q.front();
		q.pop();
		if(lo>hi||v.empty())continue;
		int mid=(lo+hi)>>1;
		if(mid<pv)rt->reset(),pv=0;
		while(pv<mid){
			++pv;
			if(l[pv]<=r[pv])rt->up(l[pv],r[pv],a[pv]);
			else rt->up(l[pv],m,a[pv]),rt->up(1,r[pv],a[pv]);
		}
		vi lv,rv;
		for(int x:v){
			ll tot=0;
			for(int i:s[x]){
				tot+=rt->qry(i);
				if(tot>=p[x])break;
			}
			if(tot>=p[x])lv.pb(x),ans[x]=mid;
			else rv.pb(x);
		}
		q.push({lo,mid-1,lv});
		q.push({mid+1,hi,rv});
	}
	for(int i=1;i<=n;++i){
		if(ans[i]==-1)pf("NIE\n");
		else pf("%d\n",ans[i]);
	}
}

Compilation message

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

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7508 KB	Output is correct
2	Correct	6 ms	7508 KB	Output is correct
3	Correct	8 ms	7532 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	7508 KB	Output is correct
2	Correct	6 ms	7508 KB	Output is correct
3	Correct	7 ms	7508 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	358 ms	15532 KB	Output is correct
2	Correct	519 ms	17020 KB	Output is correct
3	Correct	506 ms	16928 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	446 ms	16492 KB	Output is correct
2	Correct	455 ms	16496 KB	Output is correct
3	Correct	525 ms	16960 KB	Output is correct
4	Correct	81 ms	15208 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	15904 KB	Output is correct
2	Correct	233 ms	17508 KB	Output is correct
3	Correct	64 ms	8624 KB	Output is correct
4	Correct	439 ms	17292 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	155 ms	15436 KB	Output is correct
2	Correct	341 ms	16696 KB	Output is correct
3	Correct	403 ms	15864 KB	Output is correct
4	Correct	527 ms	18156 KB	Output is correct

Subtask #7
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4936 ms	57732 KB	Output is correct
2	Correct	281 ms	52108 KB	Output is correct
3	Correct	486 ms	12764 KB	Output is correct
4	Execution timed out	6070 ms	65536 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5412 ms	56880 KB	Output is correct
2	Correct	731 ms	52316 KB	Output is correct
3	Correct	90 ms	13124 KB	Output is correct
4	Runtime error	4924 ms	65536 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-