oj.uz

답안 #347762

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

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

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

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

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

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

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

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

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