Submission #102730

#	Time	Username	Problem	Language	Result	Execution time	Memory
102730		bakpark	Meteors (POI11_met)	C++14	74 / 100	4161 ms	66560 KiB

met

#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <vector>
using namespace std;
#define ll long long
struct quer{
	int l,r;
	ll val;
};

int N,M,Q;
ll tree[2000000];
ll need[300005];
quer q[300005];
vector<int> arr[300005];
vector<int> bs[300005];
int L[300005],R[300005],answ[300005];
int MAX=1;

void push(int x,int l,int r,int LL,int RR,ll val){
	if(r<LL||RR<l) return;
	if(LL<=l&&r<=RR){
		tree[x]+=val;
		return;
	}
	int m = (l+r)>>1;
	push(x<<1,l,m,LL,RR,val);
	push((x<<1)+1,m+1,r,LL,RR,val);
}
ll get(int pos){
	ll sum = 0;
	int x = MAX-1+pos;
	while(x>0){
		sum+=tree[x];
		x = x>>1;
	}
	return sum;
}

int main(){
	scanf("%d %d",&N,&M);
	while(MAX<M){
		MAX = MAX<<1;
	}
	for(int i=1;i<=M;i++){
		int tmp;
		scanf("%d",&tmp);
		arr[tmp].push_back(i);
	}
	for(int i=1;i<=N;i++) scanf("%lld",&need[i]);
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++) {
		scanf("%d %d %lld",&q[i].l,&q[i].r,&q[i].val);
	}
	for(int i=1;i<=N;i++){
		L[i] = 1;
		R[i] = Q;
		answ[i] = -1;
		bs[(Q+1)>>1].push_back(i);
	}
	bool flag = true;
	while(flag){
		memset(tree,0,sizeof(tree));
		flag = false;
		for(int i=1;i<=Q;i++){
			int l = q[i].l,r = q[i].r;
			ll val = q[i].val;
			if(l<=r){
				push(1,1,MAX,l,r,val);
			}
			else{
				push(1,1,MAX,l,M,val);
				push(1,1,MAX,1,r,val);
			}
			for(int ver:bs[i]){
				ll sum = 0;
				bool done = false;
				for(int pos:arr[ver]){
					sum+=get(pos);
					if(sum>=need[ver]){
						R[ver] = i-1;
						answ[ver] = i;
						done = true;
						break;
					}
				}
				if(!done) L[ver] = i+1;
				if(L[ver]<=R[ver]){
					int m = (L[ver]+R[ver])>>1;
					bs[m].push_back(ver);
					if(m<i) flag = true;
				}
			}
			bs[i].clear();
		}
	}
	for(int i=1;i<=N;i++){
		if(answ[i]==-1) printf("NIE\n");
		else printf("%d\n",answ[i]);
	}
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~~
met.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&tmp);
   ~~~~~^~~~~~~~~~~
met.cpp:51:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%lld",&need[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
  ~~~~~^~~~~~~~~
met.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&q[i].l,&q[i].r,&q[i].val);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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