oj.uz

Submission #1092880

# Submission time Handle Problem Language Result Execution time Memory
1092880 2024-09-25T09:38:33 Z Sunbae Fountain (eJOI20_fountain) C++17
30 / 100
 83 ms 9776 KB 
#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
vector<int> v[N];
ll qs[N];
int d[N], st[N], idx[N], C[N], vis[N], nxt[N], sz, c; 
signed main(){
	int n, 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 > 0 && d[st[sz-1]] <= d[i]) --sz;
		nxt[i] = (sz > 0) ? 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){
		sz = v[i].size();
		for(int j = 0; j<sz; ++j){
			idx[v[i][j]] = j;
			if(j > 0) qs[v[i][j]] += qs[v[i][j-1]];
		}
	}
	while(q--){
		int i, w; scanf("%d %d", &i, &w); --i; 
		c = C[i]; 
		ll rem = (idx[i] > 0) ? qs[v[c][idx[i]-1]] : 0;
		int low = idx[i], high = v[c].size() - 1, ans = -1;
		while(low <= high){
			int mid = low + ((high-low)>>1);
			ll tmp = qs[v[c][mid]] - rem;
			if(tmp >= w) ans = v[c][mid], high = mid-1;
			else if(tmp < w) low = mid+1;
		}
		printf("%d\n", ans + 1);
	}
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:10:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  int n, 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:33:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   int i, w; scanf("%d %d", &i, &w); --i;
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9776 KB Output is correct
2 Correct 83 ms 9744 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -