Submission #347762

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
347762	2021-01-13T11:08:26 Z	algorithm16	Meteors (POI11_met)	C++14	100 / 100	1434 ms	33404 KB

#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

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.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	9568 KB	Output is correct
2	Correct	162 ms	11360 KB	Output is correct
3	Correct	112 ms	9696 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	141 ms	9568 KB	Output is correct
2	Correct	137 ms	9568 KB	Output is correct
3	Correct	163 ms	10848 KB	Output is correct
4	Correct	33 ms	9324 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	9604 KB	Output is correct
2	Correct	178 ms	10964 KB	Output is correct
3	Correct	180 ms	8556 KB	Output is correct
4	Correct	114 ms	9952 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	9312 KB	Output is correct
2	Correct	144 ms	9568 KB	Output is correct
3	Correct	93 ms	9440 KB	Output is correct
4	Correct	149 ms	10720 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1048 ms	29260 KB	Output is correct
2	Correct	651 ms	23276 KB	Output is correct
3	Correct	862 ms	14044 KB	Output is correct
4	Correct	1296 ms	30032 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1012 ms	26624 KB	Output is correct
2	Correct	640 ms	20588 KB	Output is correct
3	Correct	687 ms	14052 KB	Output is correct
4	Correct	1434 ms	33404 KB	Output is correct