oj.uz

Submission #753059

# Submission time Handle Problem Language Result Execution time Memory
753059 2023-06-04T14:03:46 Z emad234 Fountain (eJOI20_fountain) C++17
60 / 100
 365 ms 57180 KB 
#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 2e5 + 1;
pair<ll,ll> a[mxN];
pair<ll,ll> st[mxN][32];

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  ll n,t;
  cin >>n>>t;
  for(ll i = 0;i < n;i++){
    cin >>a[i].first>>a[i].second;
  }
  a[n] = {1e10,1e10};
  n++;
  priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q;
  for(ll i = 0;i < n;i++){
    while(q.size() && a[i].first > q.top().first){
      st[q.top().second][0] = {a[i].second,i};
      // cout<<q.top().second<<' '<<q.top().first<<' '<<i<<'\n';
      q.pop();
    }
    q.push({a[i].first,i});
  }
  st[n][0] = {1e10,n};
  for(ll k = 1;k < 32;k++){
    for(ll i = 0;i < n;i++){
      st[i][k] = {st[st[i][k - 1].second][k - 1].first + st[i][k - 1].first,st[st[i][k - 1].second][k - 1].second};
    }
  }
  while(t--){
    ll p,c;
    cin >>p>>c;
    // cout<<'\n';
    p--;
    c -= a[p].second;
    for(ll k = 31;k >= 0;k--){
      if(st[p][k].first < c){
        // cout<<p<<' '<<st[p][k].second<<' '<<c<<'\n';
        c -= st[p][k].first;
        p = st[p][k].second;
      }
    }
    if(c > 0)
      p = st[p][0].second;
    if(p == n - 1) p = -1;
    cout<<p + 1<<'\n';
  }
}































//                                                                  nice

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 692 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 864 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 53156 KB Output is correct
2 Correct 311 ms 49400 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 692 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 864 KB Output is correct
8 Correct 279 ms 53156 KB Output is correct
9 Correct 311 ms 49400 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 136 ms 31372 KB Output is correct
12 Correct 365 ms 57180 KB Output is correct
13 Incorrect 214 ms 56240 KB Output isn't correct
14 Halted 0 ms 0 KB -