제출 #640815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640815		maks007	Fountain (eJOI20_fountain)	C++14	60 / 100	614 ms	524288 KiB

fountain

#include "bits/stdc++.h"
#define int long long
#define N (int)1e5
 
int next[N+1];
std::pair <int,int> where[N+1];
std::vector <std::vector <int>> Pref;
std::vector <std::vector <int> > who;
 
signed main () {
	for(int i = 0; i <= N; i ++) where[i] = {-1,-1};
	int n, q;
	std::cin >> n >> q;
	int d[n], c[n];
	for(int i = 0; i < n; i ++) std::cin >> d[i] >> c[i];
	std::priority_queue <std::pair <int,int> > s;
	for(int i = 0; i < n; i ++) {
		if(s.size() == 0) {
			s.push({-d[i], i});
		}else {
			while(s.empty() ==0 and -(s.top()).first < d[i]) {
				std::pair <int,int> cur = s.top();
				s.pop();
				next[cur.second] = i;
				if(s.size() == 0) break;
			}
			s.push({-d[i], i});
		}
	}
	while(s.size() > 0) {
		next[(s.top()).second] = n;
		s.pop();
	}
	for(int i = 0; i < n; i ++) {
		if(where[i].first != -1) continue;
		std::vector <int> pref;
		pref.push_back(c[i]);
		where[i] = {Pref.size(), 0};
		std::vector <int> forwho;
		forwho.push_back(i+1);
		for(int j = next[i]; j != n; j = next[j]) {
			if(j == n) break;
			if(next[j] > 1e5) break;
			pref.push_back(pref.back() + c[j]);
			forwho.push_back(j+1);
			where[j] = {Pref.size(),pref.size()-1};
		}
		Pref.push_back(pref);
		who.push_back({});
		for(auto j : forwho) {
			who.back().push_back(j);
		}
	}
	while(q --) {
		int v, r;
		std::cin >> v >> r;
		std::swap(v, r);
		r --;
		int l = 0, rr = Pref[where[r].first].size()-1;
		while(l < rr) {
			int m = (l + rr)/2;
			if(where[r].first >= N) while(true);
			if(m >= (int)Pref[where[r].first].size()) while(true);
			
			if(Pref[where[r].first][m] - (where[r].second==0?0:Pref[where[r].first][where[r].second-1]) >= v) rr = m;
			else l = m + 1;
		}
		if(Pref[where[r].first].back()< v) std::cout << 0LL << "\n";
		else {
			if(where[r].first> who.size() ) while(1);
			std::cout << who[where[r].first][rr] << "\n";
		}
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fountain.cpp: In function 'int main()':
fountain.cpp:70:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    if(where[r].first> who.size() ) while(1);
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40