Submission #673771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
673771	2022-12-22T02:07:01 Z	vjudge1	Meteors (POI11_met)	C++14	74 / 100	193 ms	65536 KB

#include<stdio.h>
#include<vector>
#define N 300001
using namespace std;
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
struct node{int data,l,r;}tre[N*60];
int n,m,q,sz,p[N],rt[N];vector<int>e[N];
inline void make(int&i,const int&l,const int&r,const int&ql,
	const int&qr,const int&a)
{
	if(qr<l||r<ql)return;
	tre[++sz]=tre[i];i=sz;
	if(ql<=l&&r<=qr)tre[i].data+=a;
	else
	{
		int mid=l+r>>1;
		make(tre[i].l,l,mid,ql,qr,a);
		make(tre[i].r,mid+1,r,ql,qr,a);
	}
}
inline void query(int i,int l,int r,const int&q,long long&wr)
{
	for(;i;)
	{
		wr+=tre[i].data;
		if(l==r)break;
		int mid=l+r>>1;
		if(q<=mid)r=mid,i=tre[i].l;
		else l=mid+1,i=tre[i].r;
	}
}
main()
{
	read(n);read(m);
	for(int i=0,x;i<m;read(x),e[--x].push_back(i++));
	for(int i=0;i<n;read(p[i++]));
	read(q);
	for(int i=1,l,r,a;i<=q;++i)
	{
		read(l);read(r);read(a);--l;--r;
		if(l<=r)make(rt[i]=rt[i-1],0,m-1,l,r,a);
		else make(rt[i]=rt[i-1],0,m-1,r+1,l-1,-a),tre[rt[i]].data+=a;
	}
	for(int i=0,l,r,mid;i<n;++i)
	{
		l=1;r=q;
		for(long long sum;l<=r;)
		{
			mid=l+r>>1;sum=0;
			for(int j=0;j<e[i].size()&&sum<p[i];++j)
				query(rt[mid],0,m-1,e[i][j],sum);
			if(sum>=p[i])r=mid-1;
			else l=mid+1;
		}
		if(l>q)printf("NIE\n");
		else printf("%d\n",l);
	}
}

Compilation message

met.cpp: In function 'void make(int&, const int&, const int&, const int&, const int&, const int&)':
met.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   int mid=l+r>>1;
      |           ~^~
met.cpp: In function 'void query(int, int, int, const int&, long long int&)':
met.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid=l+r>>1;
      |           ~^~
met.cpp: At global scope:
met.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main()
      | ^~~~
met.cpp: In function 'int main()':
met.cpp:58:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |    mid=l+r>>1;sum=0;
      |        ~^~
met.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for(int j=0;j<e[i].size()&&sum<p[i];++j)
      |                ~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7508 KB	Output is correct
2	Correct	5 ms	7636 KB	Output is correct
3	Correct	5 ms	7612 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7680 KB	Output is correct
2	Correct	4 ms	7636 KB	Output is correct
3	Correct	5 ms	7636 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	32536 KB	Output is correct
2	Correct	129 ms	33744 KB	Output is correct
3	Correct	193 ms	33324 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	105 ms	33664 KB	Output is correct
2	Correct	128 ms	33632 KB	Output is correct
3	Correct	90 ms	33788 KB	Output is correct
4	Correct	39 ms	10264 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	21772 KB	Output is correct
2	Correct	72 ms	37580 KB	Output is correct
3	Correct	26 ms	20564 KB	Output is correct
4	Correct	117 ms	33448 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	33028 KB	Output is correct
2	Correct	84 ms	33380 KB	Output is correct
3	Correct	88 ms	32844 KB	Output is correct
4	Correct	126 ms	33916 KB	Output is correct

Subtask #7
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	137 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	153 ms	65536 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-