Submission #1092868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092868		Sunbae	Fountain (eJOI20_fountain)	C++17	30 / 100	92 ms	8652 KiB

fountain

#include <bits/stdc++.h>
#define z exit(0)
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
ll qs[N];
int d[N], st[N], nxt[N], vis[N], C[N], idx[N], c, sz, n;
vector<int> v[N];
signed main(){
	int q; scanf("%d %d", &n, &q);
	for(int i = 0; i<n; ++i) scanf("%d %lld", d+i, qs+i);
	for(int i = n-1; i>=0; --i){
		while(sz && d[st[sz-1]] <= d[i]) --sz;
		nxt[i] = sz ? st[sz-1] : n;
		st[sz++] = i;
	}
	for(int i = 0; i<n; ++i){
		if(vis[i]) continue;
		for(int j = i; j < n; j = nxt[j], vis[j] = 1) v[C[j] = c].push_back(j);
		++c;
	}
	for(int i = 0; i<c; ++i) for(int j = 1; j<v[i].size(); ++j) qs[v[i][j]] += qs[v[i][j-1]], idx[v[i][j]] = j;
	while(q--){
		int st; ll w; scanf("%d %lld", &st, &w); c = C[--st]; 
		int low = idx[st], high = v[c].size() - 1, ans = -1;
		while(low <= high){
			int mid = low + ((high-low)>>1);
			ll tmp = qs[v[c][mid]] - (idx[st] ? qs[v[c][idx[st]-1]] : 0);
			if(w < tmp){
				ans = v[c][mid]; high = mid-1; 
			}else if(w == tmp){
				ans = v[c][mid]; break;
			}else if(w > tmp){
				low = mid+1;
			}
		}
		printf("%d\n", ans+1);
	}
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:22:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 0; i<c; ++i) for(int j = 1; j<v[i].size(); ++j) qs[v[i][j]] += qs[v[i][j-1]], idx[v[i][j]] = j;
      |                                          ~^~~~~~~~~~~~
fountain.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  int q; scanf("%d %d", &n, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~~
fountain.cpp:11:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  for(int i = 0; i<n; ++i) scanf("%d %lld", d+i, qs+i);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:24:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   int st; ll w; scanf("%d %lld", &st, &w); c = C[--st];
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~

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