oj.uz

답안 #673771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 153 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -