oj.uz

Submission #1022657

# Submission time Handle Problem Language Result Execution time Memory
1022657 2024-07-13T21:27:42 Z Arpi2007 Fountain (eJOI20_fountain) C++17
100 / 100
 160 ms 22868 KB 
#include <iostream>
#include <queue>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <math.h>
#include <climits>
#include <iomanip>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define ld long double
#define ull unsigned long long
#define ub upper_bound
#define lb lower_bound 
#define ff first
#define ss second
#define mpr make_pair
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define vpi vector<pii>
#define pb push_back
#define pob pop_back
#define mii map<int,int>
#define vpl vector<pair<ll, ll>>
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define sz(x) x.size()
#define clr(x) x.clear()
#define yes cout << "YES\n"
#define no cout << "NO\n"
//ifstream cin("bcount.in");
//ofstream cout("bcount.out");
 
void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
void setprecision(int x) {
 
    cout.setf(ios::fixed | ios::showpoint);
    cout.precision(x);
}
 
/*void setIO(string name = "") {
    if ((int)name.size() > 0) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}*/
 
ll gcd(ll a, ll b) {
    if (a > b) {
        swap(a, b);
    }
    if (a == 0) {
        return b;
    }
    if (a == b) {
        return a;
    }
    return gcd(b - a, a);
}
 
ll num(ll n) {
    ll ans = 0;
    while (n != 0) {
        ans++;
        n /= 10;
    }
    return ans;
}
 
ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}
 
ll MOD = 1e9 + 7;
ll MOD2 = 998244353;
 
ll factorial(ll n) {
    ll ans = 1;
    for (int i = 1; i <= n; i++) {
        ans *= i;
        ans %= MOD2;
    }
    return ans;
}
ll fact2(ll n, ll k) {
    ll ans = 1;
    for (int i = 1; i <= n; i++) {
        if (i == k) {
            ans *= (k - 1);
        }
        else {
            ans *= i;
        }
        ans %= MOD2;
    }
    return ans;
}
 
bool isPrime(int n)
{
    if (n <= 1) {
        return false;
    }
    if (n == 2) {
        return true;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

ll bpow_mod(ll a, ll b, ll mod)
{
  ll ans = 1;
  while (b) {
    if ((b & 1) == 1) {
      ans *= a;
     ans %= mod;
    }
    b >>= 1;
    a *= a;
    a %= mod;
  }
  return ans;
}

 
bool sortbysec(const pair<int, int>& a,
    const pair<int, int>& b)
{
    return (a.second < b.second);
}
 
bool ask(vector<int> vertices) {
    cout << "? " << vertices.size();
    for(int x: vertices) {
        cout << " " << x;
    }
    cout << endl << flush;
    string answer;
    cin >> answer;
    return (answer == "YES");
}

void precalc(){
    return;
}

const int N = 3e5 + 10;
ll a[N];
ll ans[N];
int d[N], c[N];
int up[N][20], pref[N][20];

void solve() {
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        cin >> d[i] >> c[i];
    }
    vi v;
    stack<pii>st;
    int cur = 0;
    st.push({1e9, 0});
    c[0] = d[0] = 1e9;
    for(int i = n; i >= 1; --i){
        while(st.top().ff <= d[i]){
            st.pop();
        }
        up[i][0] = st.top().ss;
        pref[i][0] = c[st.top().ss];
        for(int j = 1; j <= 17; ++j){
            up[i][j] = up[up[i][j - 1]][j - 1];
            pref[i][j] += pref[i][j - 1] + pref[up[i][j - 1]][j - 1];
        }
        st.push({d[i], i});
    }
    while(q--){
        int r, val; cin >> r >> val;
        if(c[r] >= val){
            cout << r << endl;continue;
        }
        val -= c[r];
        for(int i = 16; i >= 0; --i){
            if(pref[r][i] < val){
                val -= pref[r][i];
                r = up[r][i];
            }
        }
        cout << up[r][0] << "\n";
    }
}


void cases() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }  
}
 
int main() {
    fastio();
    precalc();
    //cases();
    solve();
    return 0;
}

Compilation message

fountain.cpp: In function 'void solve()':
fountain.cpp:178:9: warning: unused variable 'cur' [-Wunused-variable]
  178 |     int cur = 0;
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 20356 KB Output is correct
2 Correct 97 ms 19280 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 85 ms 20356 KB Output is correct
9 Correct 97 ms 19280 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 47 ms 11752 KB Output is correct
12 Correct 124 ms 22868 KB Output is correct
13 Correct 110 ms 21812 KB Output is correct
14 Correct 98 ms 21012 KB Output is correct
15 Correct 160 ms 21076 KB Output is correct