oj.uz

Submission #640692

# Submission time Handle Problem Language Result Execution time Memory
640692 2022-09-15T06:17:01 Z maks007 Fountain (eJOI20_fountain) C++14
60 / 100
 517 ms 524288 KB 
#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;
	scanf("%lld%lld", &n, &q);
	int d[n], c[n];
	for(int i = 0; i < n; i ++) scanf("%lld%lld", &d[i], &c[i]);
	std::set <std::pair <int,int> > s;
	s.insert({INT_MAX, INT_MAX});
	for(int i = 0; i < n; i ++) {
		if(s.size() == 0) {
			s.insert({d[i], i});
		}else {
			while((*s.begin()).first < d[i]) {
				std::pair <int,int> cur = *s.begin();
				s.erase(s.begin()); 
				next[cur.second] = i;
			}
			s.insert({d[i], i});
		}
	}
	while(s.size() > 1) {
		next[(*s.begin()).second] = n;
		s.erase(s.begin());
	}
	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]) {
			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;
		scanf("%lld%lld", &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(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() - (where[r].second==0?0:Pref[where[r].first][where[r].second-1]) < v) printf("0\n");
		else printf("%lld\n", who[where[r].first][rr]);
	}
	return 0;
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%lld%lld", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
fountain.cpp:15:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  for(int i = 0; i < n; i ++) scanf("%lld%lld", &d[i], &c[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%lld%lld", &v, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 2004 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 2 ms 2004 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8000 KB Output is correct
2 Correct 87 ms 7632 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 2004 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 2 ms 2004 KB Output is correct
8 Correct 80 ms 8000 KB Output is correct
9 Correct 87 ms 7632 KB Output is correct
10 Correct 2 ms 2004 KB Output is correct
11 Runtime error 517 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -