oj.uz

Submission #926533

# Submission time Handle Problem Language Result Execution time Memory
926533 2024-02-13T08:30:07 Z vin Fountain (eJOI20_fountain) C++14
30 / 100
 82 ms 25476 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

const int INF = 2147483645;
const int maxN = (int)2e5+5;
const ll LLINF = LLONG_MAX;
const ll mod = 998244353;
//const ll mod = 1000000007;

vector<ll> pre[maxN], preidx[maxN];
ll idx[maxN], inidx[maxN];

void solv() {
	ll n, q, a, b;
	vector<pll> v;
	cin>>n>>q;
	for (int i=0;i<n;i++) {
		cin>>a>>b; v.pb(mp(a, b));
	}
	set< pair<ll, pll> > s;
	ll itr = 1;
	for (int i=n-1;i>=0;i--) {
		bool ers = false;
		ll cur = v[i].first;
		ll cap = v[i].second;
		while (!s.empty() && cur >= (*s.begin()).first) {
			ers = true;
			s.erase(*s.begin());
		}
		if (ers) itr++;
		s.insert(mp(cur, mp(cap, i+1)));
		idx[i+1] = itr;
		pre[itr].pb(cap);
		preidx[itr].pb(i+1);
	}
	for (int i=0;i<pre[itr].size();i++) s.erase(*s.begin());
	itr++;
	for (auto i: s) pre[itr].pb(i.second.first), preidx[itr].pb(i.second.second), idx[i.second.second] = itr;
	for (int i=1;i<=itr;i++) {
		if (i != itr) reverse(pre[i].begin(), pre[i].end()), reverse(preidx[i].begin(), preidx[i].end());
		for (int j=0;j<pre[i].size();j++) {
			inidx[preidx[i][j]] = j;
			if (!j) continue;
			pre[i][j] += pre[i][j-1];
		}
	}
	
//	for (int i=1;i<=itr;i++) {
//		for (auto j: pre[i]) cout<<j<<" ";
//		cout<<'\n';
//	}
	
	for (int i=0;i<q;i++) {
		bool dbl = false;
		ll ans;
		cin>>a>>b;
		int chk = idx[a], inchk = inidx[a];
		if (inchk) b += pre[chk][inchk-1];
		if (b > pre[chk][pre[chk].size()-1]) dbl = true, b-=pre[chk][pre[chk].size()-1];
		if (dbl) {
			int last = preidx[chk][preidx[chk].size()-1];
			int newchk = upper_bound(preidx[itr].begin(), preidx[itr].end(), last) - preidx[itr].begin();
			if (newchk) b += pre[itr][newchk-1];
			if (b > pre[itr][pre[itr].size()-1]) ans = 0;
			else {
				int ansidx = lower_bound(pre[itr].begin(), pre[itr].end(), b) - pre[itr].begin();
				ans = preidx[itr][ansidx];
			}
		} else {
			int ansidx = lower_bound(pre[chk].begin(), pre[chk].end(), b) - pre[chk].begin();
			ans = preidx[chk][ansidx];
		}
		cout<<ans<<'\n';
	}
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t=1;
//    cin>>t;
    while (t--) solv();
}

Compilation message

fountain.cpp: In function 'void solv()':
fountain.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i=0;i<pre[itr].size();i++) s.erase(*s.begin());
      |               ~^~~~~~~~~~~~~~~~
fountain.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int j=0;j<pre[i].size();j++) {
      |                ~^~~~~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 25476 KB Output is correct
2 Correct 82 ms 24952 KB Output is correct

Subtask #3
0 / 40.0

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