oj.uz

Submission #976039

# Submission time Handle Problem Language Result Execution time Memory
976039 2024-05-06T05:51:06 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 353 ms 39784 KB 
#include <bits/stdc++.h>
using namespace std; 
#define int long long 
#define fi first 
#define se second 
#define pb push_back
pair<int,int>a[100005]; 
vector<pair<int,int>>que[100005]; 
vector<int>adj[100005]; 
int ans[200005]; 
vector<int>nodes; 
vector<int>pref; 
int n, q; 
void dfs(int node){
    //cout << "here >> " << node << endl; 
    nodes.pb(node); 
    if(node == n + 1)pref.pb(0); 
    else pref.pb(pref.back() + a[node].se); 
    for(auto it : que[node]){
        int l = 1, r = pref.size() - 1, ret = -1;
        while(l <= r){
            int mid = (l+r)/2; 
            if(pref[pref.size()-1] - pref[mid-1] >= it.fi){
                ret = mid; 
                l = mid + 1; 
            }
            else{
                r = mid - 1; 
            }
        }
        //cout << "here1 >> " << it.fi << " " << ret << endl; 
        if(ret == -1)ans[it.se] = 0; 
        else ans[it.se] = nodes[ret]; 
    }
    for(auto it : adj[node])dfs(it); 
    pref.pop_back(); 
    nodes.pop_back(); 
}
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cin >> n >> q; 
    for(int i = 1; i <= n; i++){
        cin >> a[i].fi >> a[i].se; 
    }
    for(int i = 1; i <= q; i++){
        int x,y; cin >> x >> y; 
        que[x].pb({y,i}); 
    }
    vector<pair<int,int>>v; 
    for(int i = 1; i <= n; i++){
        v.push_back({a[i].fi,i}); 
    }
    sort(v.begin(),v.end(),greater<pair<int,int>>()); 
    set<int>s; 
    s.insert(n+1); 
    vector<int>tmp; 
    for(int i = 0; i < n; i++){
        int node = v[i].se; 
        int idx = *s.upper_bound(node); 
        adj[idx].pb(node); 
        tmp.pb(node); 
        if(i == n - 1 || v[i].fi != v[i+1].fi){
            for(auto it : tmp)s.insert(it); 
            tmp.clear(); 
        }
    }
    dfs(n+1); 
    for(int i = 1; i <= q; i++){
        cout << ans[i] << endl; 
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6632 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 5 ms 6744 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 32512 KB Output is correct
2 Correct 293 ms 34476 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6632 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 5 ms 6744 KB Output is correct
8 Correct 225 ms 32512 KB Output is correct
9 Correct 293 ms 34476 KB Output is correct
10 Correct 4 ms 6748 KB Output is correct
11 Correct 161 ms 18124 KB Output is correct
12 Correct 339 ms 39784 KB Output is correct
13 Correct 353 ms 28716 KB Output is correct
14 Correct 338 ms 25664 KB Output is correct
15 Correct 302 ms 24768 KB Output is correct