Submission #347762

#	Time	Username	Problem	Language	Result	Execution time	Memory
347762		algorithm16	Meteors (POI11_met)	C++14	100 / 100	1434 ms	33404 KiB

met

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int llint;
int o[300005],arr[300005],sol[300005];
llint fwt[300005],n,m,k;
vector <pair<pair<int,int>,llint> > v;
vector <int> ind[300005],v1;
void update(int x,llint v) {
	for(x;x<300005;x+=x&-x) fwt[x]+=v;
}
llint query(int x) {
	llint ret=0;
	for(x;x>0;x-=x&-x) ret+=fwt[x];
	return ret;
}
void f(int l,int r,llint v) {
	if(l<=r) {
		update(l,v);
		update(r+1,-v);
	}
	else {
		update(l,v);
		update(m+1,-v);
		update(1,v);
		update(r+1,-v);
	}
	//cout << query(1) << " " << query(2) << " " << query(3) << " " << query(4) << " " << query(5) << "\n";
}
llint eval(int x) {
	llint ret=0;
	for(int i=0;i<ind[x].size();i++) {
		ret+=query(ind[x][i]+1);
		if(ret>=arr[x]) break;
	}
	return ret;
}
void rek(int lo,int hi) {
	//cout << lo1 << " " << hi1 << "\n";
	//system("pause");
	if(lo>hi) {
		for(int i=0;i<v1.size();i++) {
			sol[v1[i]]=-1;
		}
		return;
	}
	if(lo==hi) {
		for(int i=0;i<v1.size();i++) {
			sol[v1[i]]=lo;
		}
		return;
	}
	int mid=(lo+hi)/2;
	for(int i=lo;i<=mid;i++) {
		f(v[i].first.first,v[i].first.second,v[i].second);
	}
	vector <int> l,r;
	for(int i=0;i<v1.size();i++) {
		if(eval(v1[i])>=arr[v1[i]]) l.push_back(v1[i]);
		else r.push_back(v1[i]);
	}
	//cout << l.size() << " " << r.size() << "\n";
	//cout << lo1 << " " << mid << " " << mid+1 << " " << hi1 << "\n";
	//system("pause");
	v1=r;
	rek(mid+1,hi);
	for(int i=lo;i<=mid;i++) {
		f(v[i].first.first,v[i].first.second,-v[i].second);
	}
	v1=l;
	rek(lo,mid);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i=0;i<m;i++) {
		cin >> o[i];
		ind[o[i]-1].push_back(i);
	}
	for(int i=0;i<n;i++) {
		cin >> arr[i];
		v1.push_back(i);
	}
	cin >> k;
	for(int i=0;i<k;i++) {
		llint l,r,a;
		cin >> l >> r >> a;
		v.push_back(make_pair(make_pair(l,r),a));
	}
	//cout << "abc\n";
	//system("pause");
	rek(0,k);
	for(int i=0;i<n;i++) {
		if(sol[i]==k) cout << "NIE\n";
		else cout << sol[i]+1 << "\n";
	}
	return 0;
}

Compilation message (stderr)

met.cpp: In function 'void update(int, llint)':
met.cpp:11:6: warning: statement has no effect [-Wunused-value]
   11 |  for(x;x<300005;x+=x&-x) fwt[x]+=v;
      |      ^
met.cpp: In function 'llint query(int)':
met.cpp:15:6: warning: statement has no effect [-Wunused-value]
   15 |  for(x;x>0;x-=x&-x) ret+=fwt[x];
      |      ^
met.cpp: In function 'llint eval(int)':
met.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i=0;i<ind[x].size();i++) {
      |              ~^~~~~~~~~~~~~~
met.cpp: In function 'void rek(int, int)':
met.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i=0;i<v1.size();i++) {
      |               ~^~~~~~~~~~
met.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i=0;i<v1.size();i++) {
      |               ~^~~~~~~~~~
met.cpp:59:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i=0;i<v1.size();i++) {
      |              ~^~~~~~~~~~

• 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: 13 / 13
• Subtask 8: 13 / 13